MathOverflow is a question and answer site for professional mathematicians. 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

I would like to ask whether there is a combinatorial proof of the following recurrence relation for Catalan numbers: $$ C_{n+1}=\frac{4n+2}{n+2} C_n. $$


share|cite|improve this question
As no motivation is given, I expect it's a curiosity question. I would suggest to look at Ira Gessel's articles discussing combinatorics of the Catalan numbers (for example, mentioned in the question but also in the answer of Timothy Chow there). – Wadim Zudilin Aug 2 '10 at 11:38
I have thought about this (out of curiosity) and I didn't come up with anything so I would be interested in any answers. – Bruce Westbury Aug 2 '10 at 12:54
I give up: the newcomers don't care of reading the corresponding wiki pages. So, it's just losing time. For nothing. :-( – Wadim Zudilin Aug 2 '10 at 13:30
Bruce, how many of the 66 definitions listed in Stanley's "Enumerative combinatorics" did you consider? – Victor Protsak Aug 4 '10 at 5:35
I think giving a combinatorial proof sometimes is a bit tricky. Using not proper interpretations and methods may easily lead to a dead end. – Thomas Li Aug 4 '10 at 8:49
up vote 9 down vote accepted

What you are asking is reported as fourth proof in the wiki article for the formula of the Catalan numbers:

share|cite|improve this answer
Quite nice proof. I am trying to make a bijection from the polygon interpretation to the noncrossing matching interpretation. My goal is to give a proof in the language of noncrossing matching. – Thomas Li Aug 2 '10 at 16:34

these papers can you help:

share|cite|improve this answer
Thanks for the first link! I could clearly understand how 'the number of different ways a convex polygon with n + 2 sides can be cut into triangles by connecting vertices with straight lines' problem is solved. I just, cant seem to understand the wiki proof! – Spai Jul 24 '12 at 8:05

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.