8.1 \(Catalan\) 数
先见识一下 \(Catalan\) 数长啥样——
\(C_0=1,C_1=1,C_2=2,C_3=5,C_4=14,C_5=42,C_6=132...\)
一些公式及推导
1) \(C_0=1, C_n=\sum\limits_{i=0}^{n-1} C_i \times C_{n-i-1}\) \((n\geq 1)\)
许多应用中都用到该式子。
2） \(C_n=\frac{1}{n+1}\binom{2n}{n}\)
由1）推导一下。
设 \({C_n}\) 的生成函数为 \(F(x)=C_0+C_1x+C_2x^2+...+C_kx^k+...\)
则 \[ \begin{equation*} \begin{aligned} (F(x))^2&=C_0^2+(C_0C_1+C_1C_0)x+(C_0C_2+C_1C_1+C_2C_0)x^2+...+(\sum\limits_{i=0}^{k} C_i \times C_{k-i})x^k+... \\ &=C_1+C_2x+C_3x^2+...+C_{k+1}x^k+... \\ &=\frac{F(x)-C_0}{x}=\frac{F(x)-1}{x} \end{aligned} \end{equation*} \]
即 \((F(x))^2-\frac{1}{x}F(x)+\frac{1}{x}=0\)
解得 \(F(x)=\frac{1-\sqrt{1-4x}}{2x}\) （取正负看收敛性）
由牛顿二项式定理可知 \((1+z)^{\frac{1}{2}}=1+\sum\limits_{i=1}^{\infty} \frac{(-1)^{i-1}}{i\times 2^{2i-1}}\binom{2i-2}{i-1}z^i\) \((|z|<1)\)
(该式推导可在这里找)
则 \[ \begin{equation*} \begin{aligned} F(x)&=-\frac{1}{2x}\sum\limits_{i=1}^{\infty} \frac{(-1)^{i-1}}{i\times 2^{2i-1}}\binom{2i-2}{i-1}(-1)^i4^ix^i \\ &=\sum\limits_{i=1}^{\infty} \frac{1}{i}\binom{2i-2}{i-1}x^{i-1} \end{aligned} \end{equation*} \]
即 \(C_{n-1}=\frac{1}{n}\binom{2n-2}{n-1}\) \((n\geq 1)\)
则 \(C_n=\frac{1}{n+1}\binom{2n}{n}\) \((n\geq 0)\)
3） \(C_0=1, C_n=\frac{4n-2}{n+1}C_{n-1}\) \((n\geq 1)\)
直接带2）进去：\(\frac{C_n}{C_{n-1}}=\frac{n\binom{2n}{n}}{(n+1)\binom{2n-2}{n-1}}=\frac{n(2n)!(n-1)!(n-1)!}{(n+1)(2n-2)!n!n!}=\frac{4n-2}{n+1}\)
定理
考虑由 \(n\) 个1和 \(n\) 个-1构成的 \(2n\) 项序列 \(a_1,a_2,...,a_{2n}\)
其部分和总满足 \(a_1+a_2+...+a_k\geq 0\) \((k=1,2,...,2n)\)
的序列个数等于第 \(n\) 个 \(Catalan\) 数 \(C_n=\frac{1}{n+1}\binom{2n}{n}\)
证明一：
序列总个数为 \(\binom{2n}{n}\) ，设其中不满足要求的由 \(U_n\) 个，满足的由 \(A_n\) 个。
则 \(A_n=\binom{2n}{n}-U_n\) ，考虑如何求 \(U_n\)
设 \(k\) 为不满足要求的序列中第一个 \(a_1+a_2+...+a_k<0\) 的下标，则 \(a_1+a_2+...+a_{k-1}=0\)，\(a_k=-1\)
前 \(k\) 项中有 \(\frac{k-1}{2}\) 个1，\(\frac{k+1}{2}\) 个-1
将前 \(k\) 项各自取相反数，则新数列中有 \((n+1)\) 个1和 \((n-1)\) 个-1
设 \(h\) 为新数列中首个 \(a_1+a_2+...+a_h>0\) 的下标（由于新数列中1比-1个数多，\(h\) 一定存在），则 \(h=k\)
将前 \(h\) 项再各自取相反数便得到原序列。
则 \((n+1)\) 个1和 \((n-1)\) 个-1的排列与 \(U_n\) 中的排列一一对应。
所以 \(U_n=\binom{2n}{n-1}\)
\(A_n=\binom{2n}{n}-\binom{2n}{n-1}=\frac{(2n)!}{n!(n-1)!}(\frac{1}{n}-\frac{1}{n+1})=\frac{1}{n+1}\binom{2n}{n}\)
证明二：
设 \(k\) 为满足要求的序列中的首个 \(a_1+a_2+...+a_{2k}=0\) ，则 \(k\in [1,n],k\in Z\)
设 \(A_n\) 为满足要求的序列个数。
则 \(A_n=\sum\limits_{i=1}^n A_{n-i}A_{i-1}=\sum\limits_{i=0}^{n-1} A_iA_{n-i+1}\)
所以 \({A_n}\) 即为卡特兰数列。
应用
我懒得写了。推荐下别人的戳这里