Appearance
递推方程与生成函数是离散数学的"代数武器"：递推方程刻画序列规律并用于算法复杂度分析，生成函数把计数问题转化为幂级数运算。本笔记覆盖常系数线性递推的求解、生成函数应用、Catalan 数与 Stirling 数。
递推方程基础
定义与实例
递推方程把 aₙ 与前面的 aᵢ 联系起来，配合初值唯一确定序列：
| 实例 | 递推方程 | 初值 | 解 |
|---|---|---|---|
| Fibonacci | fₙ = fₙ₋₁ + fₙ₋₂ | f₀=1, f₁=1 | 特征根法 |
| 阶乘 | F(n) = nF(n−1) | F(1)=1 | n! |
| Hanoi 塔 | T(n) = 2T(n−1)+1 | T(1)=1 | 2ⁿ−1 |
| 插入排序 | W(n) = W(n−1)+n−1 | W(1)=0 | O(n²) |
| 归并排序 | W(n) = 2W(n/2)+n−1 | W(1)=0 | O(n log n) |
常系数线性齐次递推方程（重点）
标准形与特征方程
- 标准形：aₙ + c₁aₙ₋₁ + … + cₖaₙ₋ₖ = 0（k 阶）
- 特征方程：xᵏ + c₁xᵏ⁻¹ + … + cₖ = 0，其根为特征根
通解结构（核心考点）
| 特征根情况 | 通解形式 |
|---|---|
| 无重根 q₁,…,qₖ | aₙ = c₁q₁ⁿ + c₂q₂ⁿ + … + cₖqₖⁿ |
| q 是 e 重根 | 对应部分 (c₁ + c₂n + … + cₑnᵉ⁻¹)qⁿ |
求解步骤：① 写特征方程 → ② 求特征根 → ③ 写通解 → ④ 代入初值定常数。
例：fₙ=fₙ₋₁+fₙ₋₂ 的特征方程 x²−x−1=0，特征根为黄金比 (1±√5)/2。
常系数线性非齐次递推方程（重点）
通解 = 齐次通解 + 一个特解
特解形式（考点）
| f(n) 形式 | 特解假设 |
|---|---|
| n 次多项式 | 一般也是 n 次多项式（必要时升阶） |
| βⁿ 且 β 不是特征根 | P·βⁿ |
| βⁿ 且 β 是 e 重特征根 | P·nᵉ·βⁿ |
| 组合形式 | 各成分特解相加 |
例：Hanoi T(n)=2T(n−1)+1，特解设常数 P，得 P=−1，通解 T(n)=c·2ⁿ−1，由 T(1)=1 得 c=1。
其他解法
| 方法 | 适用 | 要点 |
|---|---|---|
| 换元法 | 变系数方程 | 换元化成常系数线性 |
| 迭代归纳/递归树 | 分治型 T(n)=aT(n/b)+d(n) | 展开每层代价求和 |
| 差消法 | 化简递推方程 | 两式相减消去和式 |
| 尝试法 | 验证猜测 | 代入检查 |
分治递推（主定理式结论）
T(n) = aT(n/b) + d(n)：
- d(n)=c（常数）→ T(n) = O(log n)（二分搜索）
- d(n)=cn → T(n) = O(n log n)（归并排序）
- a=bᵏ 且 d(n)=O(nᵏ) → T(n) = O(nᵏ log n)
- a>bᵏ → T(n) = O(n^(log_b a))（如位乘 3W(n/2)+cn → O(n^1.59)）
生成函数（重点）
定义与性质
- 生成函数：G(x) = a₀ + a₁x + a₂x² + …（序列 {aₙ} 的生成函数）
- 常用：{C(m,n)} 的生成函数 (1+x)ᵐ；{kⁿ} 的生成函数 1/(1−kx)
- 性质：线性性、平移（乘以 x）、求导（bₙ=naₙ ⇔ B(x)=xA′(x)）、卷积（和序列）
应用（考点）
- 求解递推方程：G(x) 与 xG(x)、x²G(x) 组合消去递推 → 解出 G(x) → 展开求 aₙ
- 计数多重集 r-组合数：(1+y+…+yⁿ¹)(1+y+…+yⁿ²)… 中 yʳ 的系数
- 不定方程解的个数：带上下限、带系数的方程 → 各因子乘积的系数
- 整数拆分：无序拆分（每部分一个因子）、有序拆分 C(N−1, r−1)
指数生成函数
E(x) = Σ aₙxⁿ/n!，用于排列类计数。多重集 r-排列数 = Π(1 + x/1! + x²/2! + … + xⁿᵢ/nᵢ!) 中 xʳ/r! 的系数。
Catalan 数与 Stirling 数（考点）
Catalan 数 Cₙ
- 定义：凸 n+1 边形三角剖分数；初值 C₂=1（也有 C₀=1 的约定）
- 递推：Cₙ₊₁ = Σ Cₖ·Cₙ₋ₖ（k 从 0 到 n）
- 通项：Cₙ = C(2n,n)/(n+1)
- 等价组合问题：n 个数的栈输出个数、不穿过对角线的非降路径数（2Cₙ）、n 对括号的合法匹配数、有序三度根树数
Stirling 数
- 第一类 s(n,k)：n 个元素排成 k 个循环排列（圆排列）的方法数；递推 s(n,k) = s(n−1,k−1) + (n−1)s(n−1,k)
- 第二类 S(n,k)：把 n 个不同元素分成 k 个非空子集的方法数；递推 S(n,k) = S(n−1,k−1) + k·S(n−1,k)
- 应用：满射计数 n!·S(m,n)；n 个球放 m 个盒子的全表（见下）
放球模型总表
| 球 | 盒 | 是否空盒 | 计数 |
|---|---|---|---|
| 同 | 同 | 否/是 | 整数拆分 |
| 同 | 异 | 否/是 | C(n−1,m−1) / C(n+m−1,n) |
| 异 | 同 | 否/是 | S(n,m) |
| 异 | 异 | 否/是 | m!·S(n,m) / mⁿ |
一句话总结
齐次递推用特征根写通解、非齐次先找特解再并齐次解；生成函数把计数变成"找系数"；Catalan 数递推+通项必背，放球模型表是计数题的总开关。
相关概念
- 离散数学-组合计数 — 非降路径与 Catalan 数
- 离散数学-容斥原理 — 错排递推 Dₙ 的求解
- 离散数学-图与树 — 树的遍历与递归结构
- 离散数学-数论与概率应用 — 快速排序平均复杂度的递推分析