卡特兰数、格路径与生成函数

课程视频

背景介绍

想象你站在一个 \(n \times n\) 网格的左下角，想要走到右上角。每一步你只能向右或向上移动。总共有多少条路径？这是一个经典的组合数学热身题：\(\binom{2n}{n}\)。但如果我们加一个限制条件——你的路径永远不能越过主对角线上方呢？满足条件的”合法”路径数就是一个卡特兰数，这是一个在数学中无处不在的数列：出现在表达式的括号化中、二叉树的结构中、多边形的三角剖分中，以及更多地方。

在本课中，我们用两种完全不同的方法推导卡特兰数的封闭公式。首先，我们使用一个优美的反射论证（安德烈反射原理），将计算”非法”路径的问题转化为一个简单的网格计数问题。然后我们基于合法路径首次接触对角线的位置建立递推关系，并发现该递推是非线性的——与我们之前求解过的任何递推都不同。这促使我们引入生成函数，一个强大的代数工具，它将整个数列编码成一个多项式（或幂级数），让我们能像操作函数一样操作数列。

Important核心要点

1. 网格路径：从 \((0,0)\) 到 \((n,n)\) 的格路径数（仅使用向右和向上步）为 \(\binom{2n}{n}\)。
2. 卡特兰数：其中不越过主对角线上方的路径数为 \(C_n = \frac{1}{n+1}\binom{2n}{n}\)。
3. 安德烈反射原理：每条”越界”路径都可以关于直线 \(y = x + 1\) 进行反射，建立与到达偏移目的地的所有路径的一一对应，从而得到 \(C_n = \binom{2n}{n} - \binom{2n}{n-1}\)。
4. 卡特兰递推：\(C_n = \displaystyle\sum_{j=0}^{n-1} C_j \cdot C_{n-1-j}\)，基于首次接触对角线的点的非线性递推。
5. 生成函数：形式幂级数 \(G(x) = \displaystyle\sum_{k=0}^{\infty} C_k \, x^k\) 编码了所有卡特兰数；\(G(x)\) 的平方再现了递推中的卷积，从而得到 \(G(x) = x\,G(x)^2 + 1\)。

在网格上计数路径

考虑一个 \(n \times n\) 网格。我们从角 \(A = (0,0)\) 出发，想要到达角 \(B = (n,n)\)。每一步要么向右（R）要么向上（U）。每条路径恰好由 \(2n\) 步组成——\(n\) 步向右和 \(n\) 步向上——所以我们要从 \(2n\) 个位置中选择哪 \(n\) 个位置为”向右”：

\[\text{总路径数} = \binom{2n}{n}\]

Tip示例：在网格上填充帕斯卡三角

在一个 \(4 \times 4\) 网格上，将每个格点标注从 \((0,0)\) 到该点的路径数。底行和左列全为 \(1\)。每个内部点是其左邻居和下邻居之和——恰好是构建帕斯卡三角的规则。角点的值为 \(\binom{8}{4} = 70\)。

卡特兰约束：保持在对角线下方

如果一条路径从未严格越过主对角线 \(y = x\) 的上方，则该路径是合法的。等价地，在路径上的每一点，已走的向上步数从未超过向右步数。

前几个卡特兰数为：

\(n\)	0	1	2	3	4	5
\(C_n\)	1	1	2	5	14	42

注意 \(C_3 = 5\)，而不是 \(6\)，并且它必须是奇数：每条合法路径都有一个镜像（交换 R 和 U，然后反转），而有一条在对角线上的路径映射到自身。这个奇偶论证可以推广。

安德烈反射原理

我们不直接计算合法路径，而是计算非法（越界）路径，然后用总数减去。

第 1 步：找到首次越界点

每条非法路径必须在某点穿过直线 \(y = x\)，即触碰直线 \(y = x + 1\)。将首次触碰点记为 \(P\)。

第 2 步：反射剩余路程

从 \(P\) 点开始，将路径的剩余部分关于直线 \(y = x + 1\) 进行反射。这将后续的每个 R 步与 U 步互换。反射后的路径终点不再是 \(B = (n, n)\)，而是一个新点：

\[B^* = (n-1,\, n+1)\]

第 3 步：建立双射

这种反射是可逆的：给定任何从 \(A\) 到 \(B^*\) 的路径，它必定在某处穿过直线 \(y = x + 1\)（因为它的终点在该线上方）。从首次穿越点进行反射即可恢复出唯一的从 \(A\) 到 \(B\) 的越界路径。因此：

\[\text{（到 } B \text{ 的非法路径数）} = \text{（到 } B^* \text{ 的所有路径数）}\]

第 4 步：计算并相减

从 \((0,0)\) 到 \((n-1, n+1)\) 的路径数为 \(\binom{2n}{n+1}\)，因为我们仍然走 \(2n\) 步，但现在选择 \(n+1\) 步向上（或等价地选择 \(n-1\) 步向右）。

\[C_n = \binom{2n}{n} - \binom{2n}{n+1}\]

Note证明：化简为封闭公式

\[C_n = \binom{2n}{n} - \binom{2n}{n+1}\]

用阶乘写出每个二项式系数：

\[C_n = \frac{(2n)!}{n!\,n!} - \frac{(2n)!}{(n+1)!\,(n-1)!}\]

提取公因子 \(\frac{(2n)!}{n!\,n!}\)：

\[C_n = \frac{(2n)!}{n!\,n!}\left(1 - \frac{n!}{(n+1)!} \cdot \frac{n!}{(n-1)!}\right) = \binom{2n}{n}\left(1 - \frac{n}{n+1}\right) = \binom{2n}{n} \cdot \frac{1}{n+1}\]

因此：

\[\boxed{C_n = \frac{1}{n+1}\binom{2n}{n}}\]

Tip示例：验证 \(C_4 = 14\)

\[C_4 = \frac{1}{5}\binom{8}{4} = \frac{1}{5} \cdot 70 = 14\]

或者：\(C_4 = \binom{8}{4} - \binom{8}{5} = 70 - 56 = 14\)。两种方法一致。

渐近行为

合法路径占所有路径的比例为：

\[\frac{C_n}{\binom{2n}{n}} = \frac{1}{n+1}\]

随着 \(n\) 增大，这个比例趋向于零。当 \(n = 100\) 时，仅约 \(1\%\) 的路径保持在对角线下方。直觉上，在大网格上的随机游走几乎必然会在某一点越过对角线。

卡特兰递推

有一种完全不同的方法来推导卡特兰数：基于首次接触对角线的递推。

建立递推关系

考虑 \(n \times n\) 网格上的一条合法路径。观察该路径离开 \((0,0)\) 后首次接触主对角线的位置。假设首次接触发生在点 \((j+1,\, j+1)\)，其中 \(0 \le j \le n-1\)。

• 从 \((0,0)\) 到 \((j+1, j+1)\) 的路径被迫以一步向右开始，以一步向上结束（否则它会更早接触对角线）。中间部分是 \(j \times j\) 网格上的一条合法路径：共有 \(C_j\) 条这样的路径。
• 从 \((j+1, j+1)\) 到 \((n, n)\) 的路径是 \((n-1-j) \times (n-1-j)\) 网格上的一条合法路径：共有 \(C_{n-1-j}\) 条这样的路径。

对所有可能的首次接触位置求和：

\[\boxed{C_n = \sum_{j=0}^{n-1} C_j \cdot C_{n-1-j}}\]

其中 \(C_0 = 1\)。

Tip示例：用递推验证 \(C_4\)

\[C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0\] \[= 1 \cdot 5 + 1 \cdot 2 + 2 \cdot 1 + 5 \cdot 1 = 5 + 2 + 2 + 5 = 14 \checkmark\]

为什么这个递推很难

这是一个非线性递推——每一项是两个更早的卡特兰数的乘积，并且我们对一个滑动窗口求和。将其与线性递推（如斐波那契数列 \(F_n = F_{n-1} + F_{n-2}\)）相比较，后者可以使用特征多项式的特征值求解。这里没有这样的直接方法可用。

回顾：求解线性递推

在引入处理卡特兰递推所需的强大工具之前，让我们回顾如何处理线性递推。

给定如下递推关系：

\[7F_{n+1} = 6F_n + F_{n-1} + 5\]

第 1 步：吸收常数。 定义平移数列 \(G_n = F_n - a\)，选择 \(a\) 使常数项消失。如果常数可以被吸收（即 \(1\) 不是特征值），我们就可以化简为齐次递推。

第 2 步：特征方程。 对于 \(G_{n+1} = \alpha G_n + \beta G_{n-1}\)，猜测 \(G_n = r^n\) 并求解二次方程 \(r^2 = \alpha r + \beta\) 得到特征值 \(r_1, r_2\)。

第 3 步：通解。 解为线性组合：

\[G_n = A \cdot r_1^n + B \cdot r_2^n\]

其中 \(A\) 和 \(B\) 由初始条件确定。如果 \(r_1, r_2\) 是复数，则解涉及旋转（振幅和相位），这我们之前已经学过。

Tip示例：什么时候无法吸收常数？

考虑 \(7F_{n+1} = 6F_n + F_{n-1} + 4\)。令 \(G_n = F_n - a\)，我们需要 \(7a = 6a + a + 4\)，即 \(0 = 4\)。这不成立，因为 \(r = 1\) 是特征方程 \(7r^2 - 6r - 1 = 0\) 的一个根（验证：\(7 - 6 - 1 = 0\)）。在这种情况下，我们使用不同的代换——改为尝试 \(G_n = F_n - an\)，引入线性平移来处理共振情况。

生成函数：非线性递推的关键

由于卡特兰递推是非线性的，我们需要新的工具。生成函数是一个形式幂级数，将整个数列打包成一个代数对象：

\[G(x) = \sum_{k=0}^{\infty} C_k \, x^k = C_0 + C_1 x + C_2 x^2 + C_3 x^3 + \cdots\]

我们不关心代入 \(x\) 的具体值或级数是否收敛。幂级数只是一个容器——正如我们使用复数作为角度信息的容器一样，我们使用 \(G(x)\) 作为卡特兰数列的容器。

卷积的联系

卡特兰递推 \(C_n = \sum_{j=0}^{n-1} C_j \cdot C_{n-1-j}\) 看起来恰好像将两个 \(G(x)\) 相乘后 \(x^{n-1}\) 的系数的公式。当你计算 \(G(x)^2\) 时：

\[G(x)^2 = \left(\sum_{k=0}^{\infty} C_k x^k\right)^2 = \sum_{n=0}^{\infty} \left(\sum_{j=0}^{n} C_j C_{n-j}\right) x^n\]

\(G(x)^2\) 中 \(x^n\) 的系数是 \(\sum_{j=0}^{n} C_j C_{n-j}\)，这恰好就是 \(C_{n+1}\)！

这意味着：

\[G(x)^2 = \frac{G(x) - C_0}{x} = \frac{G(x) - 1}{x}\]

整理后：

\[\boxed{x \, G(x)^2 - G(x) + 1 = 0}\]

这是一个关于 \(G(x)\) 的二次方程！用求根公式可以得到 \(G(x)\) 的封闭表达式，从中我们可以提取 \(C_n\) 作为 \(x^n\) 的系数。这是本课的作业探索——尝试将 \(G(x)\) 平方，观察规律的出现。

Note预告：求解 \(G(x)\) 的二次方程

将 \(G(x)\) 视为 \(xG^2 - G + 1 = 0\) 中的未知量，求根公式给出：

\[G(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}\]

我们选择负号（这样在取极限后 \(G(0) = C_0 = 1\)）。使用广义二项式定理展开 \(\sqrt{1 - 4x}\)，即可恢复出公式 \(C_n = \frac{1}{n+1}\binom{2n}{n}\) 作为 \(x^n\) 的系数。完整推导将在下一课完成。

课程关键帧

速查表

概念	公式 / 规则
网格路径 \((0,0) \to (n,n)\)	\(\binom{2n}{n}\)
卡特兰数（封闭公式）	\(C_n = \frac{1}{n+1}\binom{2n}{n}\)
卡特兰数（减法形式）	\(C_n = \binom{2n}{n} - \binom{2n}{n+1}\)
卡特兰递推	\(C_n = \displaystyle\sum_{j=0}^{n-1} C_j \cdot C_{n-1-j}\)，\(C_0 = 1\)
前几个卡特兰数	\(1, 1, 2, 5, 14, 42, 132, 429, \ldots\)
合法路径比例	\(\frac{C_n}{\binom{2n}{n}} = \frac{1}{n+1}\)
生成函数	\(G(x) = \displaystyle\sum_{k=0}^{\infty} C_k x^k\) 满足 \(xG(x)^2 - G(x) + 1 = 0\)
安德烈反射目的地	越界路径与到 \((n-1, n+1)\) 的所有路径构成双射
线性递推特征值	\(a_n = A r_1^n + B r_2^n\)，其中 \(r_1, r_2\) 是特征方程的根

快速参考：卡特兰数数值

\(n\)	\(C_n\)	\(\binom{2n}{n}\)	合法路径比例
0	1	1	1
1	1	2	1/2
2	2	6	1/3
3	5	20	1/4
4	14	70	1/5
5	42	252	1/6
6	132	924	1/7