$$C_{n} = \sum_{i=1}^n (-1)^{i-1} \binom{n-i+1}{i} C_{n-i}$$
Are there any good combinatorial proofs or algebraic proofs of this?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ Obvious comment: looks like some kind of inclusion-exclusion... $\endgroup$– Sam HopkinsMay 6 at 20:26
-
14$\begingroup$ I rolled back your edit; you asked for a proof and received a proof; please don't change the question afterwards. $\endgroup$– Carlo BeenakkerMay 6 at 21:09
-
3$\begingroup$ This is not research level. It is more appropriate for math.stackexchange.com. $\endgroup$– PatrickRMay 8 at 19:18
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
$C_n$ is the number of Catalan sequences $(x_1,\ldots,x_{2n})$ of $\pm 1$ with zero sum and non-negative prefix sums $x_1+\ldots+x_k$, for $k=1,\ldots,2n$. Note that any such sequence contains an index $j\in \{1,2,\ldots,n\}$ for which $x_j=1$, $x_{j+1}=-1$. Call $(j,j+1)$ a special pair. Then ${n-i+1\choose i}$ is the number of ways to choose $i$ special pairs (they are of course disjoint), and $C_{n-i}$ is the number of Catalan sequences with these $i$ pairs being special. Then your identity is just inclusion-exclusion. Note that the same argument shows that $$C_n=\sum_i (-1)^{i-1}{n+1+t-i\choose i}C_{n-i}$$ for every $t=0,1,\ldots,n-1$, if we consider special pairs with $j\in \{1,2,\ldots,n+t\}$.
answered May 6 at 20:49
-
1$\begingroup$ Could you explain why there are nCr (𝑛−𝑖+1, i) number of ways to choose 𝑖 special pairs? $\endgroup$– bananaMay 6 at 23:59
-
2$\begingroup$ @banana Consider the $i$ pairs $j,j+1$ as $i$ boxes (which may includes $n+1$ as well). Now put the remaining $n-2i+1$ numbers can be arranged in $i+1$ ( the places in between the boxes and on the sides) in $\binom{n-i+1}{i}$ ways. $\endgroup$ May 7 at 4:49
-
4$\begingroup$ if $j_1<j_2<\ldots<j_i$ are first elements of $i$ special pairs, then $j_1<j_2-1<j_3-2<\ldots <j_i-i+1\leqslant n-i+1$ are distinct numbers between 1 and $n-i+1$ $\endgroup$ May 7 at 6:17
$\begingroup$
$\endgroup$
Algebraically, this identity is $$\sum_{n=0}^\infty C(n) x^n (1-x)^{n+1} = 1, $$ which is a consequence of the generating function $$\sum_{n=0}^\infty C(n) x^n = \frac{1-\sqrt{1-4x}}{2x}.$$
