特殊计数序列—

Catalan数

\(1,1,2,5,14,42,132,429,1430,4862\)

（注：从第\(0\)项起）

大家都知道结论：\(C_n=\frac{1}{n+1}\dbinom{2n}{n}\)，在这里给出证明

考虑从相反的方面进行考虑，即用总序列数\(\dbinom{2n}{n}\)减去不合法的序列数

对于每一个不合法的序列，必定存在一个最小的\(k\)使得\(\sum_{i=1}^k a_i<0\)，也就是有\(\sum_{i=0}^{k-1}a_i=0\)且\(a_k=-1\)

很明显\(k\)是奇数

考虑将前\(k\)项取相反数，那么该序列变成了一个含有\(n+1\)个\(+1\)和\(n-1\)个\(-1\)的序列，容易知道一个不合法的原序列只会对应一个新序列

同理，在新序列中一定会存在一个\(k\)使得\(\sum_{i=0}^ka_i=1\)，此时再一次取前\(k\)项的相反数，又会得到一个不合法的原序列

因此不合法的序列和新序列是一一映射的关系，而新序列的总数也就是\(\dbinom{2n}{n-1}\)

于是最终答案就是\(\dbinom{2n}{n}-\dbinom{2n}{n-1}=\frac{1}{n+1}\dbinom{2n}{n}\)

由这一条组合意义可以引申出许多本质一样的组合意义

在网格图上从\((0,0)\)走到\((n,n)\)，每次只走一个单位长度，不走回头路，且不穿过（可碰到）直线\(y=x\)的方案数。（向右：\(+1\)，向上：\(-1\)）
\(2n\)个人排队买票，票价5角，有\(n\)个人持有1元硬币，另\(n\)个人持有\(5\)角硬币，求不使用额外的\(5\)角钱的排队方案（\(5\)角：\(+1\)，\(1\)元：\(-1\)）

这是上面的第二个式子\(C_{n+1}=\sum_{i=0}^nC_iC_{n-i}\)，我们有\(f_n=\sum_{i=2}^{n-1}f_if_{n-i-1}\)，故\(f_n=C_{n+2}\)

类似的还有

本质上和第一点是相同的，关键是对偶数位置的转化