第 10 章 · 递推与生成函数

很多计数问题给得出递推关系(第 k+1 项由前面项决定)却看不出通项:斐波那契、卡特兰数、汉诺塔。本章给两套把递推变成公式的机器:特征方程(线性递推的直通车)与生成函数(把数列编码成多项式,用代数操作解计数问题)。生成函数是组合数学的「终极武器」,也是数据结构课第 10 章(动态规划优化)与算法课(平均复杂度分析)的数学后盾。

10.1 递推关系:计数问题的自然形态

回顾两个老朋友(第 7 章):

汉诺塔:T(n) = 2T(n−1) + 1,T(1) = 1 → T(n) = 2ⁿ − 1(累加法展开即可);
斐波那契:F(n) = F(n−1) + F(n−2),F(0)=0, F(1)=1 → 朴素递归指数爆炸(数据结构课第 9 章),通项公式本章揭晓。

线性常系数齐次递推的标准形:aₙ = c₁aₙ₋₁ + … + cₖaₙ₋ₖ。解法三步:写出特征方程 rᵏ = c₁rᵏ⁻¹ + … + cₖ,求根,按根组装通项。

10.2 特征方程:斐波那契的通项

斐波那契的特征方程:r² = r + 1,即 r² − r − 1 = 0,两根 r = (1±√5)/2(黄金比 φ ≈ 1.618 与其孪生)。通项(比内公式):

$F(n) = \frac`{\varphi^n - \hat\varphi^n}``{\sqrt{5}}`$

验证 F(0) = 0、F(1) = 1(代入即证),归纳可证对所有 n 成立(第 4 章)。几个推论:φⁿ/√5 主导,所以 F(n) ≈ φⁿ/√5,斐波那契相邻项之比趋于黄金比;F(n) 是 Θ(φⁿ)——指数级(数据结构课第 9 章「朴素递归为什么爆炸」的精确答案)。

特征方程的原理一句话:猜 aₙ = rⁿ 形式的解,代入递推得 r² = r + 1——「指数解自动满足线性递推」。重根情形(如 aₙ = 2aₙ₋₁ − aₙ₋₁):通项加一项 n·rⁿ(r 重根的补票),练习里实算。

10.3 生成函数:把数列穿成多项式

普通生成函数:数列 a₀, a₁, a₂… 编码为幂级数 G(x) = a₀ + a₁x + a₂x² + …。编码的目的:把「对数列的操作」变成「对多项式的操作」:

数列操作	生成函数操作
整体右移一位(补 0)	乘 x
相邻项相加合并	两个 G(x) 相加
卷积 cₙ = Σ aᵢbₙ₋ᵢ	相乘 G(x)·H(x)
部分和 sₙ = Σaᵢ	除以 (1−x)

几何级数是最重要的样本:1, 1, 1, … 的生成函数是 1/(1+x²)?不,是 1/(1−x)(|x| 小于 1 时收敛;形式幂级数视角下连收敛都不需要,纯代数对象)。由此得:序列 0, 1, 2, 3… 的 GF 是 x/(1−x)²,序列 1, 2, 4, 8… 是 1/(1−2x)——分母 (1−cx) 对应等比,分母的重数对应多项式因子,与 10.2 的特征方程互为表里(特征根 r ↔ 分母因子 (1−rx))。

10.4 生成函数解计数:两场演示

演示一:斐波那契的生成函数。G(x) = F₀ + F₁x + F₂x² + …,利用递推 Fₙ = Fₙ₋₁ + Fₙ₋₂ 乘 xⁿ 求和整理:

$G(x) = \frac`{x}``{1 - x - x^2}`$

部分分式分解后按等比级数展开,系数即比内公式——同一个答案,另一条更机械的路(机械意味着可自动化,计算机代数系统就这么解)。

演示二:卡特兰数(第 7 章)。递推 Cₙ = Σᵢ CᵢCₙ₋₁₋ᵢ(n ≥ 1),C₀ = 1。右边的求和恰是「GF 自乘后取 xⁿ 系数」,翻译成 GF 方程:

$C(x) = 1 + x \cdot C(x)^2$

解二次方程(取正解):C(x) = (1 − √(1−4x))/(2x),展开得:

$C_n = \frac`{1}``{n+1}`\binom`{2n}``{n}`$

递推 → 代数方程 → 闭式,计数问题的三段流水。括号匹配、出栈序列、二叉树(第 7 章的「殊途同归」)在此获得统一的解法。

10.5 回到计算机:这套数学用在哪

三处直接变现:算法平均复杂度分析(quickSort 的比较次数递推 → 生成函数/级数求和,得出 2n ln n,算法课的经典推导);DP 的优化(数据结构课第 10 章:递推的 GF 视角常揭示「可卷积」结构,分治 FFT 加速);递归式的自动求解(Mathematica/Sympy 的 rsolve 就是特征方程与 GF 的程序化)。以及一个方法论层面的收获:「难解的递推」往往缺一个「对的坐标系」,生成函数就是把数列搬到多项式坐标系的重定位操作,和第 6 章把城市搬进图、第 8 章把对称搬进群,是同一种数学行为。

常见错误

特征方程根的符号漏一半。r² − r − 1 = 0 的两根都要用,只取 φ 丢掉共轭根,数值差一个振荡项(小 n 时明显不对)。
GF 相乘当相加。卷积 = 乘法是整个方法的枢纽;「求和符号 ↔ 幂级数乘法」的对应背熟前,先手推 2×2 的小例子。
形式幂级数纠结收敛。组合 GF 是代数对象,x 只是「位置的标签」,不需要收敛;初学时最浪费时间的弯路。
初值条件漏配。递推 k 阶需要 k 个初值,少一个则解「家族」没定成员;验证 n = 0, 1, 2 三项是最便宜的试金石。

练习

用特征方程解 aₙ = 5aₙ₋₁ − 6aₙ₋₂,a₀ = 1, a₁ = 0(两根 2、3,通项 aₙ = 3ⁿ − 2ⁿ,验证前三项)。
手算:重根例子 aₙ = 2aₙ₋₁ − aₙ₋₂,a₀ = 2, a₁ = 1(根 r = 1 二重,通项 aₙ = 2 − n)。
动手:用 Python(sympy 或手写多项式类)验证「GF 相乘 = 卷积」:取 aₙ = 1、bₙ = n 的 GF 相乘,展开前 5 项,与手算卷积对比。
思考:汉诺塔 T(n) = 2T(n−1) + 1 的生成函数 T(x) = x/((1−x)(1−2x)),部分分式分解后通项 2ⁿ−1。对比「累加法」和「GF 法」两条解法,讨论「什么时候值得动用重武器」:递推复杂度到什么量级(比如耦合两个变量的二维递推)GF 的优势才压倒成本?