Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!~

share|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 mathoverflow.net/questions/26336 but also in the answer of Timothy Chow there). –  Wadim Zudilin Aug 2 '10 at 11:38
1  
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
1  
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

2 Answers 2

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: http://en.wikipedia.org/wiki/Catalan_number#Fourth_proof

share|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:

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

share|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

 
discard

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.