$$C_0 = 1,\quad C_{n+1} = C_0C_n + C_1C_{n−1}+ \cdots + C_kC_{n−k} + \cdots + C_nC_0\text{ ?}$$
Where $C_n$ denotes the number of ways of writing a valid list of open and closed parentheses of length $2n$?
Asked
Active
Viewed 938 times
1
-
Check Catalan numbers. – Mhenni Benghorbal Sep 07 '14 at 19:09
-
possible duplicate: http://math.stackexchange.com/questions/921891/proof-of-recursive-formula-for-catalan-numbers-and-their-interpretation-as-the/921955#921955 – user84413 Sep 07 '14 at 21:34
1 Answers
3
$$(1+x)^m(x+1)^m=(1+x)^{2m}$$
The coefficients of $x^m$ $$\sum_{r=0}\binom mr\binom m{m-r}=\binom{2m}m$$
lab bhattacharjee
- 274,582
-
Here used the binomial proof. But in the question he asked about Catalan number Cn, but it is not the binomial coefficient – Vamsi Spidy Dec 14 '15 at 10:58