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

Improve this question
$\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$
    – Wadim Zudilin
    Commented 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$
    – Bruce Westbury
    Commented 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$
    – Wadim Zudilin
    Commented 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$
    – Victor Protsak
    Commented 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
    Commented Aug 4, 2010 at 8:49

2 Answers 2

Reset to default
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

Improve this answer
$\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
    Commented 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

Improve this answer
$\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
    Commented Jul 24, 2012 at 8:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .