从斐波那契通项公式到卡特兰数通项公式
快速数论变换
·
·
算法·理论
前置知识：
- 强大的吃屎（读明白又臭又长的数学推导公式）能力
- 生成函数
- 二次方程
- 组合数学（请至少有少量基础并知道二项式定理就基本够了）
- 高等数学（几乎用不到）
斐波那契数列通项公式：
（此处的斐波那契数列的前两项为 f_0=f_1=1）
我们定义一个生成函数 F(x)=f_0+f_1x+f_2x^2+\cdots=\sum\limits_{i=0}^{\infty}f_ix^i，其中 f_i 为斐波那契数列第 i 项。
将 F(x) 乘上一个 x 后，可得到 xF(x)=f_0x+f_1x^2+f_2x^3+\cdots。
将 F(x) 乘上一个 x^2 后，可得到 x^2F(x)=f_0x^2+f_1x^3+\cdots。
观察出什么蹊跷了吗？如果没有，我这样写给各位观众老爷们看：
\begin{aligned}F(x)&=f_0+f_1x+f_2x^2+f_3x^3+\cdots\\xF(x)&=\,\ \ \ \ \ \ \ \ f_0x+f_1x^2+f_2x^3+\cdots\\x^2F(x)&=\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f_0x^2+f_1x^3+\cdots\end{aligned}
这下子，就很容易看出来是怎么个事了：F(x)=xF(x)+x^2F(x)。但这个等式对于第一项不满足：f_0=1，但实际上这一处为 0！所以我们要手动在等号右边补一个 1，得到 F(x)=xF(x)+x^2F(x)+1，这样这个等式就完美无缺了。
（从此处开始，F(x) 将被简写为 F）
F&=xF+x^2F+1\\
1&=F-xF-x^2F\\
F&=\dfrac{1}{1-x-x^2}
\end{aligned}
上面两步没有什么好说的，都是简单的移项。
F&=\dfrac{1}{1-x-x^2}\\
F&=\dfrac{1}{(1-c_1\cdot x)(1-c_2\cdot x)}
\end{aligned}
那这一步是在干什么呢？是在将 F 的分母进行因式分解。而我们因式分解是为了干什么呢？别急，到后面你就知道了。
但现在有一个问题，就是我们没法一眼就把它分解了。于是我们考虑拆括号，得到：1-(c_1+c_2)x+c_1c_2x=1-x-x^2，于是我们得到：
c_1+c_2=1\\
c_1\cdot c_2=-1
\end{cases}
看到这个东西，便让人不禁联想到韦达定理，于是考虑构造一个一元二次方程 ax^2+bx+c=0，使得 c_1、c_2 分别是这个方程的两个根。那根据韦达定理可得：
-\dfrac{b}{a}=1\\
\dfrac{c}{a}=-1
\end{cases}\Longrightarrow
\begin{cases}
b=-a\\
c=-a
\end{cases}
我们便能得到方程为：ax^2-ax-a=0\Longrightarrow x^2-x-1=0。
求解这个方程，得到 c_1=\dfrac{1+\sqrt{5}}{2},c_2=\dfrac{1-\sqrt{5}}{2}。
显然，c_1=\phi,c_2=-\dfrac{1}{\phi}。
则 F=\dfrac{1}{(1-\phi x)(1-(-\frac{1}{\phi})x)}。
然后，将其因式分解的作用就显现出来了：
F&=\dfrac{1}{(1-\phi x)(1-(-\frac{1}{\phi})x)}\\
&=\dfrac{d_1}{1-\phi x}+\dfrac{d_2}{1-(-\frac{1}{\phi})x}\\
&=d_1\sum\limits_{i=0}^{\infty}(\phi x)^i+d_2\sum\limits_{i=0}^{\infty}(-\frac{1}{\phi}x)^i\\
&=d_1+d_1\phi x+d_1\phi^2x^2+\cdots\\
&\,+d_2-d_2\frac{1}{\phi}x+d_2\frac{1}{\phi^2}x^2+\cdots\\
&=(d_1+d_2)+(d_1\phi-d_2\frac{1}{\phi})x+(d_1\phi^2+d_2\frac{1}{\phi^2})x^2+\cdots
\end{aligned}
很容易观察出：f_n=d_1\phi^n+d_2(-\frac{1}{\phi})^n。
而我们只需要
d_1+d_2=f_0=1\\
d_1\phi-d_2\frac{1}{\phi}=f_1=1
\end{cases}
即可求出 d_1 与 d_2。解得\begin{cases}d_1=\dfrac{\phi+1}{\phi^2+1}\\\\d_2=\dfrac{\phi^2-\phi}{\phi^2+1}\end{cases}。
则 f_n=\dfrac{\phi+1}{\phi^2+1}\phi^n+\dfrac{\phi^2-\phi}{\phi^2+1}\left(-\dfrac{1}{\phi}\right)^n
将 \phi=\dfrac{\sqrt{5}+1}{2} 代入部分 \phi 得并化简得：
f_n&=\dfrac{\frac{\sqrt{5}+1}{2}+1}{(\frac{\sqrt{5}+1}{2})^2+1}\phi^n+\dfrac{(\frac{\sqrt{5}+1}{2})^2-\frac{\sqrt{5}+1}{2}}{(\frac{\sqrt{5}+1}{2})^2+1}\left(-\dfrac{1}{\phi}\right)^n\\
&=\dfrac{\frac{\sqrt{5}+1}{2}+1}{\frac{5+2\sqrt{5}+1}{4}+1}\phi^n+\dfrac{\frac{5+2\sqrt{5}+1}{4}-\frac{\sqrt{5}+1}{2}}{\frac{5+2\sqrt{5}+1}{4}+1}\left(-\dfrac{1}{\phi}\right)^n\\
&=\dfrac{2\sqrt{5}+2+4}{5+2\sqrt{5}+1+4}\phi^n+\dfrac{5+2\sqrt{5}+1-2\sqrt{5}-2}{5+2\sqrt{5}+1+4}\left(-\dfrac{1}{\phi}\right)^n\\
&=\dfrac{6+2\sqrt{5}}{10+2\sqrt{5}}\phi^n+\dfrac{4}{10+2\sqrt{5}}\left(-\dfrac{1}{\phi}\right)^n\\
&=\dfrac{3+\sqrt{5}}{5+\sqrt{5}}\phi^n+\dfrac{2}{5+\sqrt{5}}\left(-\dfrac{1}{\phi}\right)^n\\
&=\dfrac{1}{\sqrt{5}}\left(\dfrac{3+\sqrt{5}}{\sqrt{5}+1}\phi^n+\dfrac{2}{\sqrt{5}+1}\left(-\dfrac{1}{\phi}\right)^n\right)\\
&=\dfrac{1}{\sqrt{5}}\left(\dfrac{\sqrt{5}+1}{2}\phi^n-\left(-\dfrac{\sqrt{5}-1}{2}\right)\left(-\dfrac{1}{\phi}\right)^n\right)\\
&=\dfrac{1}{\sqrt{5}}\left(\phi^{n+1}-\left(-\dfrac{1}{\phi}\right)^{n+1}\right)
\end{aligned}
于是我们就优美的将斐波那契数列的通项公式求出来了。
卡特兰数通项公式：
（此处卡特兰数前两项默认为 c_0=c_1=1）
定义一生成函数 C(x)=c_0+c_1x+c_2x^2+\ldots=\large\sum\limits_{i=0}^{\infty}\normalsize c_ix^i，其中 c_i 为第 i 个卡特兰数。
然后经过本蒟蒻好几节数学、物理、语文课 （这也导致中考时本蒟蒻物理疯狂挂分） 的推到，得到了：C^2(x)=\dfrac{C(x)-1}{x}。证明如下（从此证明开始，C(x) 简写为 C）：
注意到对 C 进行卷积后，得到的 C^2=c_1+(c_0c_1+c_1c_0)x+(c_0c_2+c_1c_1+c_2c_0)x^2+\ldots=\large\sum\limits_{i=0}^{\infty}\normalsize c_{i+1}x^i。
因为 c_0=c_1=1，所以可知：C^2=\dfrac{C-1}{x}。
然后我们按推斐波那契数列的方法，将其移项，得到：xC^2-C+1=0；然后解二次方程，得到 C=\dfrac{1\pm\sqrt{1-4x}}{2x}。
当 x\longrightarrow 0 时，C\longrightarrow c_0，且 \sqrt{1-4x}\longrightarrow1-2x-2x^2+\ldots。此时考虑加、减两种情况，看哪种成立。
- 当取减号时，即 C=\dfrac{1-\sqrt{1-4x}}{2x} 时，C\approx\dfrac{1-(1-2x-2x^2)}{2x}=1+x，在 x\longrightarrow0 时，C\longrightarrow1，正确。
- 当取加号时，即 C=\dfrac{1+\sqrt{1-4x}}{2x} 时，C\approx\dfrac{1+(1-2x-2x^2)}{2x}\approx\dfrac{1}{x}-1，在 x\longrightarrow0 时，C 显然发散，错误。
所以 C=\dfrac{1-\sqrt{1-4x}}{2x}。
但后面就出现了难题：\dfrac{1}{x} 没有对应生成函数，而 \sqrt{1-4x} 生成函数是否存在，长什么样我们都不知道，怎么办呢？
先来尝试求出 \sqrt{1-4x} 的生成函数。注意到 \sqrt{1-4x}=(1-4x)^{\frac{1}{2}}，现在大家可能都明白是怎么个事了——广义二项式定理（跟二项式定理差不太多，这里不再展开）！
所以 \sqrt{1-4x}=\large\sum\limits_{k=0}^{\infty}\normalsize\dbinom{\frac{1}{2}}{k}(-4)^kx^k。
（请自行计算 \dbinom{\frac{1}{2}}{k}。）
则：
原式&=\dfrac{1-\large\sum\limits_{k=0}^{\infty}\normalsize\dbinom{\frac{1}{2}}{k}(-4)^kx^k}{2x}\\
&=-\dfrac{1}{2}\sum\limits_{k=1}^{\infty}\dbinom{\frac{1}{2}}{k}(-4)^kx^{k-1}\ （可以代入数值计算证明正确性，此处略）\\
&=2\sum\limits_{k=0}^{\infty}\dbinom{\frac{1}{2}}{k+1}(-4)^kx^k\\
&=2\sum\limits_{k=0}^{\infty}\left[(-1)^k\dfrac{(2k)!}{2^{2k+1}k!(k+1)!}\right]\left[(-1)^k2^{2k}\right]x^k\ （用了一点展开，所以到最后我还是算了二项式系数......）\\
&=\sum\limits_{k=0}^{\infty}\dfrac{(2k)!}{(k+1)!k!}x^k\\
&=\sum\limits_{k=0}^{\infty}\dfrac{1}{k+1}\dbinom{2k}{k}x^k
\end{aligned}
然后，由定义可知：c_n=\dfrac{1}{n+1}\dbinom{2n}{n}。
我们就优雅的将卡特兰数通项公式求出来了。