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


  • $\begingroup$ 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 mathoverflow.net/questions/26336 but also in the answer of Timothy Chow there). $\endgroup$ – Wadim Zudilin Aug 2 '10 at 11:38
  • 1
    $\begingroup$ I have thought about this (out of curiosity) and I didn't come up with anything so I would be interested in any answers. $\endgroup$ – Bruce Westbury Aug 2 '10 at 12:54
  • $\begingroup$ I give up: the newcomers don't care of reading the corresponding wiki pages. So, it's just losing time. For nothing. :-( $\endgroup$ – Wadim Zudilin Aug 2 '10 at 13:30
  • 1
    $\begingroup$ Bruce, how many of the 66 definitions listed in Stanley's "Enumerative combinatorics" did you consider? $\endgroup$ – Victor Protsak Aug 4 '10 at 5:35
  • $\begingroup$ I think giving a combinatorial proof sometimes is a bit tricky. Using not proper interpretations and methods may easily lead to a dead end. $\endgroup$ – Thomas Li Aug 4 '10 at 8:49

What you are asking is reported as fourth proof in the wiki article for the formula of the Catalan numbers: http://en.wikipedia.org/wiki/Catalan_number#Fourth_proof

  • $\begingroup$ 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. $\endgroup$ – Thomas Li Aug 2 '10 at 16:34

these papers can you help:



  • $\begingroup$ 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! $\endgroup$ – Spai Jul 24 '12 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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