Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
Is this homework? What have you tried? – Matthew Conroy Mar 29 '12 at 4:45
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. – Marc van Leeuwen Mar 29 '12 at 12:14
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. – NoChance Mar 29 '12 at 14:01
@matthewConroy I just don't understand how to begin with it.It is a mess! – tamlok Mar 29 '12 at 14:12
@marcvanLeeuwen It is just an exercise in one book!And it is just like that.It is not a real program. – tamlok Mar 29 '12 at 14:15
up vote 3 down vote accepted

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$.

share|cite|improve this answer
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! – tamlok Mar 31 '12 at 10:59
@tamlok The $x$ coordinate is just the subscript of the $i$. – deinst Mar 31 '12 at 13:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.