无穷级数：把数列穿在身上
Infinite Series生成函数 F(x) = f₀ + f₁x + f₂x² + ⋯ 不再是一个"函数"，而是一件挂衣架：数列 (f₀, f₁, f₂,…) 挂在幂次上，记号 [xⁿ]F(x) := fₙ 表示"取下第 n 件"。第 14 章的扰动法轻松版本立刻见效：
最反直觉的一句话（16.1.1）：收敛与否无关紧要。n! 的生成函数在整个实数轴上只在 x=0 收敛，但它照样是合法的代数对象、照样能推出恒等式——16.5 会把这句话 axiom 化。
卷积规则：乘法就是分类讨论
Counting with Generating Functions从集合 𝒜 选取的生成函数是 A(x)，从不相交集合 ℬ 选取的是 B(x)，则"既从 𝒜 又从 ℋ 选取（总数为 n）"的生成函数就是乘积 A(x)·B(x)。因为 [xⁿ](A·B) = a₀bₙ + a₁bₙ₋₁ + ⋯ + aₙb₀——"苹果拿 k 个 × 香蕉拿 n−k 个"的全部分类，恰好是幂次对齐时那条 45° 对角线。
立刻回本：巧克力甜甜圈 C(x)=1/(1−x)、原味 P(x)=1/(1−x)，两种口味都开放时 D(x) = 1/(1−x)²——上一节硬凑的 N(x) 原来是"两种口味甜甜圈"！k 种口味推广到 1/(1−x)ᵏ，系数就是甜甜圈公式：
同一招还能重证二项式定理：单元素集 {aᵢ} 的生成函数是 1+x，m 个元素的并集就是 (1+x)ᵐ——于是 [xⁿ](1+x)ᵐ = ( m / n )。代数恒等式与计数论证开始互相供给。
荒诞计数问题：约束的乘法
An Absurd Counting Problem装一袋 n 个水果：苹果偶数个、香蕉是 5 的倍数、橙子至多 4 个、梨至多 1 个。每种约束各配一个生成函数，乘起来——
几乎全部约掉了！于是答案平凡得可笑：n+1。原书感叹 "Amazing!"——随即诚实地补一句：这个特例其实有初等证明（习题 16.8），生成函数的真正威力在下面换零钱那种没有简单答案的场合。
换零钱实验室：没有闭式，照样有答案
Making Changen 美分用 {1, 5, 10, 25, 50} 换零（习题 16.7）：每种面额的生成函数是 1/(1−x^d)（第 d 面额用几个都行），乘积的 [xⁿ] 就是方法数。这一次乘积不会约分成任何已知名状——生成函数给出的是"问题的指纹"，配合一点 DP 就能榨出每一个系数。
部分分式：通项的自动售货机
Partial Fractions荒诞水果袋的顺利纯属巧合——生成函数恰好约成 1/(1−x)²。一般问题没这么乖。Maclaurin 定理 16.2.1 倒是通用，但它要求你会求任意阶导数的闭式（往往没有）。而初等微积分里的部分分式法对"多项式之比"是全自动的：
p(x) 次数 < n，α₁,…,αₙ 互不相同且非零，则存在常数 c₁,…,cₙ：
p(x) / ((1−α₁x)(1−α₂x)⋯(1−αₙx)) = c₁/(1−α₁x) + c₂/(1−α₂x) + ⋯ + cₙ/(1−αₙx)
每项 1/(1−αᵢx) 的系数就是 αᵢⁿ（几何级数反向读）——拆完分式，通项直接读出来。原书的示范正是斐波那契的生成函数 R(x) = x/(1−x−x²)：分母求根得 α₁ = (1+√5)/2、α₂ = (1−√5)/2；由 x = c₁(1−α₂x) + c₂(1−α₁x)，分别代入 x = 1/α₁ 与 x = 1/α₂，得 c₁ = 1/√5、c₂ = −1/√5：
重根也不怕（16.3.1）：分母含 m 重非零根时，展开改用 c/(1−αx)ᵏ（k ≤ m，α 是根的倒数），系数由 donut 公式给出：[xⁿ] c/(1−αx)ᵏ = c·αⁿ·C(n+k−1, n)（式 16.13；α = 1 时就是 donut 公式 16.10 乘常数 c，一般 α 来自代入 [xⁿ]F(αx) = αⁿ·[xⁿ]F(x)）。
流程全自动：求根 → 拆分式 → 读系数。拆解器在此，三个预设覆盖互异根与重根——末尾把闭式与级数展开逐项对拍：
解线性递归：斐波那契与河内塔
Solving Linear Recurrences斐波那契：fₙ = fₙ₋₁ + fₙ₋₂, f₀=0, f₁=1。把递归两侧"错位相减"（第 14 章扰动法的家族手艺），分母自动聚成 1−x−x²：
其中 φ = (1+√5)/2 ≈ 1.618，ψ = (1−√5)/2 ≈ −0.618。这就是 Binet 公式（16.14）——看着吓人，其实右半边永远是整数；|ψ|<1，所以 fₙ 就是"离 φⁿ/√5 最近的整数"。
河内塔（16.4.2）：递归解 tₙ = 2tₙ₋₁ + 1；下界论证（大盘移动前后小盘各要让路 ≥tₙ₋₁ 步）证明它最优。生成函数 T(x) = x/((1−2x)(1−x))，部分分式 c₁=1, c₂=−1：
形式幂级数：收敛？不需要
Formal Power Seriesn! 的生成函数 F(x) = 1 + x + 2x² + 6x³ + ⋯ 在 x ≠ 0 处处处发散，但本章所有操作照样合法。理由：把无穷数列当作形式对象，配上加法 ⊕（逐位加）与乘法 ⊗（卷积），构成一个交换环——"幂级数环"。x 只是占位符，1/(1−x) = 1+x+x²+⋯ 只是陈述"K = 1/J"（J = (1,−1,0,…) 的倒数恰是全 1 序列）这个纯代数事实。收敛半径是分析学的事，与组合计数无关。
16.5.2 给了它严谨的家：数列配上逐位加 ⊕ 与卷积乘 ⊗，构成交换环——零元 Z=(0,0,…)、单位元 I=(1,0,…)。J=(1,−1,0,…) 的逆恰是 K=(1,1,1,…)（所以 1/(1−x) = 全 1 序列只是"K = 1/J"的穿衣服写法）；级数有逆 ⟺ 首项非零（Problem 16.25），Z 永远没有逆。亲手玩玩这个环：
习题实战
Practice Problems, Playable原书 Homework 16.10 的"McGillcuddy 小姐的宠物"做成两问解题器——部分分式法的完整实战。
终局自测
Final Check八题，覆盖 16.1–16.5。
彩蛋与课后挑战
Easter Eggs & Problems处处发散也挡不住的恒等式（16.5.1）
设 H(x) 为 n·n! 的生成函数。形式操作：H = (F−1)/x − F，解出 F = (xH+1)/(1−x)。卷积读系数，当场产出恒等式 n! = 1 + Σᵢ₌₁ⁿ (i−1)·(i−1)!（式 16.17）——一个"发散级数"证明的定理，第 15 章习题 15.70 还给了它组合证明。形式幂级数环：零收敛、全合法。
世界末日的精确日程（16.4.2）
64 金盘需 2⁶⁴−1 = 18,446,744,073,709,551,615 步。僧侣每秒移一盘、全年无休，也要 5,849 亿年——宇宙现龄（138 亿年）的 40 余倍。传说里"移完即世界末日"在数学上是安全的：远未到期。
平方求幂：Binet 公式的实用主义（16.4.1）
递推算 f₁₀₀₀ 要一千次加法（大数另算）；Binet 公式配平方求幂（第 6 章的 (^z mod m) 快速幂换上实数衣裳）只需 ~log₂n 次乘法。从 O(n)（一千次加法）到 O(log n)——生成函数不只好看，还真的能提速。
课后挑战（均出自原书习题）
- 16.2 求 [xⁿ] (1+x)/(1−x)²——答案 n+1 再加一签。
- 16.3 花束约束：至多 1 朵百合、郁金香奇数、玫瑰 ≥2——写出 B(x)（多项式之积即可，不必化简）。
- 16.6 S(x)=(x²+x)/(1−x)³；证明 S/(1−x) 是平方和的生成函数，推出 Σk² = n(n+1)(2n+1)/6——第 14 章猜出来的公式，这里正式付账。
- 16.9 四条甜甜圈约束的生成函数（≥3 / ≤2 / 恰好2或0 / 4的倍数），再合并闭式。
- 16.10 McGillcuddy 小姐的宠物：P(x) = 4x⁶/((1−x)²(1−2x))，求 Pₙ 闭式。