0
$\begingroup$

It is an exercise I meet in the book Discrete Mathematics Fifth Edition written by Richard.It is on page 184.It is not my homework!I just learned it by myself but I can't catch up with the solution to this problem.So thanks for helping me !It is something like this:

The pseudocede is like this :(note that "in" is just $i_n$ and n is bigger than 0 I think)

for i1: = 1 to n do   for i2: = 1 to min(i1 ,n-1) do     for i3: = 1 to min(i2,n-2) do       ...       for in-1 := 1 to min(in-2,2) do         for in := 1 to 1 do           print i1,i2,i3,...,in 

Show that print statement is executed $C_n$ times,where $C_n$ denotes the $n$th Catalan number.

I will appreciate it if you can help me!Thanks!

  • 0
    Is this homework? What have you tried?2012-03-29
  • 0
    You cannot actually statically nest $n$ for loops where $n$ is variable (the static nesting level of any program is obviously constant). However you can dynamically nest $n$ loop using recursion (do a recursive call from within a loop). Rewriting your program recursively might actually give you a hint for an inductive proof.2012-03-29
  • 0
    I think you need to edit the question so that it is clear. For example what is meant by $i_{n} in your second loop? Also, you need to give information about the range of the variable n. if n>0, the upper bounds of all for loops (except the last) will be negative.2012-03-29
  • 0
    @matthewConroy I just don't understand how to begin with it.It is a mess!2012-03-29
  • 0
    @marcvanLeeuwen It is just an exercise in one book!And it is just like that.It is not a real program.2012-03-29
  • 0
    @EmmadKareem It is clear now I think.The exercise does not specify the range of n.2012-03-29

1 Answers 1

3

Note that $i_1,\ldots,i_n$ is a nonincreasing sequence where $i_j\le n -(j-1)$, and every such sequence is generated. Read backwards, this sequence is a monotonic path from (1,1) to (n,n) that does not pass above the diagonal. See here for a few proofs that the number such monotonic paths is $C_n$.

  • 0
    Marvelous!But I can't quite understand how to make a map from one dimension(i1,i2,...) to two dimensions( (1,1) ... (n,n) )?Thanks!2012-03-31
  • 0
    @tamlok The $x$ coordinate is just the subscript of the $i$.2012-03-31