Welcome to MathOverflow

Question

3

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

edited Aug 2 2010 at 11:31

Wadim Zudilin
8,674●1●24●59

asked Aug 2 2010 at 11:27

Thomas Li
217●1●6

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 2010 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 2010 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 2010 at 13:30

1

Bruce, how many of the 66 definitions listed in Stanley's "Enumerative combinatorics" did you consider? – Victor Protsak Aug 4 2010 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 2010 at 8:49

Pietro Majer · Accepted Answer · 2010-08-02 13:16:21Z UTC

9

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

answered Aug 2 2010 at 13:16

Pietro Majer
19.7k●1●24●69

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 2010 at 16:34

Hashem sazegar · Answer 2 · 2010-08-22 08:45:03Z UTC

1

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

edited Aug 22 2010 at 8:45

Hashem sazegar

community wiki

2 revisions

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 at 8:05

Combinatorial proof of a recurrence for the Catalan numbers

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.