卡特兰数通项公式的生成函数推导
符号约定： \(C[i],[x^i]C(x)\) 表示 \(C(x)\) 的 \(x^i\) 的系数。
设 \(C[0]=1,C[n]=n\) 对括号构成的的合法括号序列数。
\[\begin{aligned} &C[n+1]=\sum_{i=0}^{n}{C[i]C[n+i]}\\ &[x^{n+1}]C(x)=[x^n]C(x)^2\\ &\frac{C(x)-1}{x}=C(x)^2\\ &C(x)=\frac{1\pm\sqrt{1-4x}}{2x}\\ \end{aligned} \]因为 \(\displaystyle\lim_{x\to 0}{C(x)=1}\)，故 \(\displaystyle C(x)=\frac{1-\sqrt{1-4x}}{2x}\)
\(\displaystyle\mathrm{Lemma}:\sqrt{1-4x}=(1-4x)^{\frac{1}{2}}=\sum_{i=0}^{\infty}(-4x)^i\binom{\frac{1}{2}}{i}=\sum_{i=0}^{\infty}{(-2)*\frac{1}{i-1}\binom{2i-2}{i}x^i}\)
\[\begin{aligned} &[x^n]x*C(x)=[x^{n}](\frac{1-\sqrt{1-4x}}{2x})\\ &[x^{n-1}]C(x)=\frac{1}{n-1}\binom{2n-2}{n}, (n\neq 1)\\ &C[n]=\frac{1}{n}\binom{2n}{n+1}=\frac{1}{n+1}\binom{2n}{n} \end{aligned} \]一个组合恒等式
\(\displaystyle \sum_{k=0}^{n}{k\binom{m-k-1}{m-n-1}}/\binom{m}{n}\)
\(Proof:\)
\[\begin{aligned} \mathrm{LHS}&=\frac{1}{\binom{m}{n}}\sum_{k=0}^{n}{(m-(m-k))\binom{m-k-1}{m-n-1}}\\ &=\frac{1}{\binom{m}{n}}\left[m\sum_{k=0}^{n}{\binom{m-k-1}{m-n-1}}-\sum_{k=0}^{n}{(m-k)\binom{m-k-1}{m-n-1}}\right]\\ &=\frac{1}{\binom{m}{n}}\left[m\binom{m}{m-n}-\sum_{k=0}^{n}(m-k)\frac{m-n}{m-k}\binom{m-k}{m-n}\right]\\ &=m-\frac{1}{\binom{m}{n}}(m-n)\sum_{k=0}^{n}{\binom{m-k}{m-n}}\\ &=m-\frac{m-n}{\binom{m}{n}}\binom{m+1}{m-n+1}\\ &=m-(m-n)\frac{m+1}{m-n+1}\\ &=\frac{n}{n+m-1} \end{aligned} \]\(Q.E.D\)
标签：frac,4x,sum,二十一日,sqrt,九月,binom,aligned,日记 From： https://www.cnblogs.com/mklzc/p/16717432.html