Catalan数
aleph_
·
·
个人记录
问题
设 h_n 表示用以下方法将凸多边形区域分成三角形区域的方法数：在有 n+1 条边的凸多边形区域内，通过插入在其中不相交的对角线而把它分成三角形区域。定义 h_1=1。求 h_n 的通项形式？
解法
Step 1：寻找递推关系
我们有 h_2=1，因为三角形不可以再分，仅 1 种方案。现在设 n\ge 3。
考虑对于一个 n+1\ge4 条边的凸多边形，先选定一条基边 AB，再选择一个边的两个端点互不相同的顶点 C，联结 AC、BC。这样就可以将原多边形分为三个部分：
-
- 三角形 ABC；
-
由于联结了 AC、BC，因此增加了 2 条边，共 n+3 条边，除去 AC 侧多边形的 k+1 条边和 1 条基边 AB，剩下的边都属于 BC 一侧的凸多边形，有 n-k+1 条。
两侧的凸多边形构成两个互相独立的子问题，其方案数分别为 h_{k} 和 h_{n-k}，则递推关系可表示为
h_n=\sum_{k=1}^{n-1}h_k h_{n-k}(n\ge 3)
递推关系也对于 n=2 成立，因为
\sum_{k=1}^{2-1}h_kh_{2-k}=\sum_{k=1}^1h_1h_1=1
Step 2：求解递推关系 I——求解生成函数
运用一般求解齐次递推关系的方法：设数列 h 的生成函数
g(x)=h_1x+h_2x^2+\cdots+h_nx^n+\cdots
将 g(x) 自乘，有
g^2(x)=h_1^2x^2+(h_1h_2+h_2h_1)x^2
+(h_1h_3+h_2h_2+h_3h_1)x^3+\cdots
+(h_1h_{n-1}+h_2h_{n-2}+\cdots+h_{n-1}h_1)x^n+\cdots
根据递推式，且利用 h_1^2=h_2=h_1=1 可得
g^2(x)=h_1^2x^2+h_3x^3+h_4x^4+\cdots+h_nx^n+\cdots
=h_2x^2+h_3x^3+h_4x^4+\cdots+h_nx^n+\cdots
=g(x)-h_1x=g(x)-x
因此 g(x) 满足方程
g^2(x)-g(x)+x=0
解得
g_1(x)=\frac{1+\sqrt{1-4x}}{2},g_2(x)=\frac{1-\sqrt{1-4x}}{2}
由 g(x) 的定义，g(x)=0，因此 g_1(x) 舍去
g(x)=\frac{1-\sqrt{1-4x}}{2}=\frac{1}{2}-\frac{1}{2}(1-4x)^{1/2}
Step 3：求解递推关系 II——求解母函数
利用牛顿二项式定理（请注意此处 k 的意义发生了变化）
(1+z)^{1/2}=\sum_{k=0}^{\infin}\binom{\frac{1}{2}}{k}z^k(|z|<1)
先求解 \binom{\frac{1}{2}}{k}
\binom{\frac{1}{2}}{k}=\frac{\frac{1}{2}(\frac{1}{2}-1)\cdots(\frac{1}{2}-k+1)}{k!}
将分子通分，共 \frac{1-2+2k}{2}+1=k 项，故提出 k-1 个 \frac{1}{2}
=\frac{(-1)^{k-1}}{2^k}\frac{1\times2\times3\times4\times\cdots\times(2k-3)\times(2k-2)}{2\times4\times\cdots\times(2k-2)\times k!}
=\frac{(-1)^{k-1}}{k\times2^{2k-1}}\frac{(2k-2)!}{(k-1)!^2}=\frac{(-1)^{k-1}}{k\times2^{2k-1}}\binom{2k-2}{k-1}
再提出第一项：\binom{\frac{1}{2}}{0}=1。因此，对 |z|<1 有
(1+z)^{1/2}=1+\sum_{k=1}^{\infin}\frac{(-1)^{k-1}}{k\times2^{2k-1}}\binom{2k-2}{k-1}z^k
如果用 -4x 代替 z，则得到
(1-4x)^{1/2}=1+\sum_{k=1}^{\infin}\frac{(-1)^{k-1}}{k\times2^{2k-1}}\binom{2k-2}{k-1}(-1)^k4^kx^k
=1+\sum_{k=1}^{\infin}(-1)^{2k-1}\frac{2}{k}\binom{2k-2}{k-1}x^k
=1-2\sum_{k=1}^{\infin}\frac{1}{k}\binom{2k-2}{k-1}x^k\left(|x|<\frac{1}{4}\right)
Therefore
g(x)=\sum_{k=1}^{\infin}\frac{1}{k}\binom{2k-2}{k-1}x^k
所以
h_n=\frac{1}{n}\binom{2n-2}{n-1}
Q.E.D