专栏文章

Catalan数

aaleph_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmgduu
此快照首次捕获于
2025/12/02 04:48
3 个月前
此快照最后确认于
2025/12/02 04:48
3 个月前
查看原文

问题

设 hnh_n 表示用以下方法将凸多边形区域分成三角形区域的方法数：在有 n+1n+1 条边的凸多边形区域内，通过插入在其中不相交的对角线而把它分成三角形区域。定义 h1=1h_1=1。求 hnh_n 的通项形式？

解法

Step 1：寻找递推关系

我们有 h2=1h_2=1，因为三角形不可以再分，仅 11 种方案。现在设 n≥3n\ge 3。
考虑对于一个 n+1≥4n+1\ge4 条边的凸多边形，先选定一条基边 ABAB，再选择一个边的两个端点互不相同的顶点 CC，联结 ACAC、BCBC。这样就可以将原多边形分为三个部分：
  1. ACAC 一侧的凸多边形，设其有 k+1k+1 条边；
  2. 三角形 ABCABC；
  3. BCBC 一侧的凸多边形。
由于联结了 ACAC、BCBC，因此增加了 22 条边，共 n+3n+3 条边，除去 ACAC 侧多边形的 k+1k+1 条边和 11 条基边 ABAB，剩下的边都属于 BCBC 一侧的凸多边形，有 n−k+1n-k+1 条。
两侧的凸多边形构成两个互相独立的子问题，其方案数分别为 hkh_{k} 和 hn−kh_{n-k}，则递推关系可表示为
hn=∑k=1n−1hkhn−k(n≥3)h_n=\sum_{k=1}^{n-1}h_k h_{n-k}(n\ge 3)
递推关系也对于 n=2n=2 成立，因为
∑k=12−1hkh2−k=∑k=11h1h1=1\sum_{k=1}^{2-1}h_kh_{2-k}=\sum_{k=1}^1h_1h_1=1

Step 2：求解递推关系 I——求解生成函数

运用一般求解齐次递推关系的方法：设数列 hh 的生成函数
g(x)=h1x+h2x2+⋯+hnxn+⋯g(x)=h_1x+h_2x^2+\cdots+h_nx^n+\cdots
将 g(x)g(x) 自乘，有
g2(x)=h12x2+(h1h2+h2h1)x2g^2(x)=h_1^2x^2+(h_1h_2+h_2h_1)x^2 +(h1h3+h2h2+h3h1)x3+⋯+(h_1h_3+h_2h_2+h_3h_1)x^3+\cdots +(h1hn−1+h2hn−2+⋯+hn−1h1)xn+⋯+(h_1h_{n-1}+h_2h_{n-2}+\cdots+h_{n-1}h_1)x^n+\cdots
根据递推式，且利用 h12=h2=h1=1h_1^2=h_2=h_1=1 可得
g2(x)=h12x2+h3x3+h4x4+⋯+hnxn+⋯g^2(x)=h_1^2x^2+h_3x^3+h_4x^4+\cdots+h_nx^n+\cdots
=h2x2+h3x3+h4x4+⋯+hnxn+⋯=h_2x^2+h_3x^3+h_4x^4+\cdots+h_nx^n+\cdots
=g(x)−h1x=g(x)−x=g(x)-h_1x=g(x)-x
因此 g(x)g(x) 满足方程
g2(x)−g(x)+x=0g^2(x)-g(x)+x=0
解得
g1(x)=1+1−4x2,g2(x)=1−1−4x2g_1(x)=\frac{1+\sqrt{1-4x}}{2},g_2(x)=\frac{1-\sqrt{1-4x}}{2}
由 g(x)g(x) 的定义，g(x)=0g(x)=0，因此 g1(x)g_1(x) 舍去
g(x)=1−1−4x2=12−12(1−4x)1/2g(x)=\frac{1-\sqrt{1-4x}}{2}=\frac{1}{2}-\frac{1}{2}(1-4x)^{1/2}

Step 3：求解递推关系 II——求解母函数

利用牛顿二项式定理（请注意此处 kk 的意义发生了变化）
(1+z)1/2=∑k=0∞(12k)zk(∣z∣<1)(1+z)^{1/2}=\sum_{k=0}^{\infin}\binom{\frac{1}{2}}{k}z^k(|z|<1)
先求解 (12k)\binom{\frac{1}{2}}{k}
(12k)=12(12−1)⋯(12−k+1)k!\binom{\frac{1}{2}}{k}=\frac{\frac{1}{2}(\frac{1}{2}-1)\cdots(\frac{1}{2}-k+1)}{k!}
将分子通分，共 1−2+2k2+1=k\frac{1-2+2k}{2}+1=k 项，故提出 k−1k-1 个 12\frac{1}{2}
=(−1)k−12k1×2×3×4×⋯×(2k−3)×(2k−2)2×4×⋯×(2k−2)×k!=\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!}
=(−1)k−1k×22k−1(2k−2)!(k−1)!2=(−1)k−1k×22k−1(2k−2k−1)=\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}
再提出第一项：(120)=1\binom{\frac{1}{2}}{0}=1。因此，对 ∣z∣<1|z|<1 有
(1+z)1/2=1+∑k=1∞(−1)k−1k×22k−1(2k−2k−1)zk(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-4x 代替 zz，则得到
(1−4x)1/2=1+∑k=1∞(−1)k−1k×22k−1(2k−2k−1)(−1)k4kxk(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+∑k=1∞(−1)2k−12k(2k−2k−1)xk=1+\sum_{k=1}^{\infin}(-1)^{2k-1}\frac{2}{k}\binom{2k-2}{k-1}x^k
=1−2∑k=1∞1k(2k−2k−1)xk(∣x∣<14)=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)=∑k=1∞1k(2k−2k−1)xkg(x)=\sum_{k=1}^{\infin}\frac{1}{k}\binom{2k-2}{k-1}x^k
所以
hn=1n(2n−2n−1)h_n=\frac{1}{n}\binom{2n-2}{n-1}

Q.E.D

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...