4
$\begingroup$

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

Thanks!~

$\endgroup$
5
  • $\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$ Aug 2, 2010 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$ Aug 2, 2010 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$ Aug 2, 2010 at 13:30
  • 1
    $\begingroup$ Bruce, how many of the 66 definitions listed in Stanley's "Enumerative combinatorics" did you consider? $\endgroup$ Aug 4, 2010 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, 2010 at 8:49

2 Answers 2

10
$\begingroup$

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

$\endgroup$
1
  • $\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, 2010 at 16:34
1
$\begingroup$

these papers can you help:

http://www.geometer.org/mathcircles/catalan.pdf

http://docs.google.com/viewer?a=v&q=cache:IPxobgy1BIcJ:www.math.ucsd.edu/~gptesler/184a/catalan_f08-handout.pdf+catalan+number&hl=en&pid=bl&srcid=ADGEESiPvWTzNFP0Z5y7CRCrf83opSMRhhCMCNSirJYnBnk_4KnLIIxe6rvj8K2DO39epTp5rZjHszeLloOot62UjlqayX96E9kw-Uw6PJ-eVbE6-rXkH-ZtxBxv6YwJrl9U9-zbJQ5F&sig=AHIEtbTXYSM6J_QnxsOMWpD1_vmFbYe7yg

$\endgroup$
1
  • $\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, 2012 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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