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
    @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
    @tamlok The $x$ coordinate is just the subscript of the $i$.2012-03-31