概念地图
递推
按某个特定元素的去向分类，把问题化归到更小的规模。
深色为本章概念，浅色为其他章
陪练模式
不想只是读？让它带你走一遍。
导师把这一章拆成小步，每一步先问你，再讲；你用自己的话答，它先认下对的部分再纠偏。用你自己的 AI，对话只存在这台设备上。
定位01
延伸阅读
斐波那契 · 十三世纪 · 兔子问题的递推
写下 \(F_n = F_{n-1} + F_{n-2}\)，是把一个计数问题化归到更小规模的最早例子之一。他反对的是逐月枚举；代价是这条递推只给出算法，没有给出通项。
奠基
棣莫弗与欧拉 · 十八世纪 · 生成函数的引入
把数列装进幂级数，使递推变成关于函数的方程，从而能解出通项。他们反对的是逐项计算；代价是收敛性问题在早期被大量忽略，直到形式幂级数的观点确立才被安置妥当。
转向
形式幂级数的观点 · 二十世纪
指出组合学里的生成函数不必收敛：它只是把数列写成一个可以做加、乘、求导的形式对象。这是对「必须先讨论收敛」的正面修正，也是本章第二条机制成立的依据。
修正
布鲁迪 · 关于递推与生成函数的章节
本课对象。教材给出解递推的标准方法，本章要说清生成函数不是新工具，而是把第 3 章那个「按什么分类」的动作自动化。
本课对象
机制02
按最后一步分类
第 3 章的手法是盯住一个特定元素。在带顺序的问题里，最有用的那个「特定元素」通常是最后一步：登上第 级台阶，最后一步要么迈了 1 级要么迈了 2 级，两类不交且穷尽，于是加法原理直接给出一条递推关系。整章的第一条机制只有这一句：换一个「按什么分类」，就换一条递推。
机制一个规模为 n 的计数问题通过按最后一步的取法分类被化归为若干更小规模的同类问题。
可迁移性测试
换到工期估算：一个 n 天的排程，按最后一天做什么分成几类，每类都变成一个 n−1 天或 n−2 天的同类问题。不同构的地方在于工程里各类之间可能有资源冲突（不真正独立），而这里要求分类不交且穷尽。
机制03
把数列装进级数
有了递推还要解它。把整个数列写成一个生成函数，递推就变成关于这个函数的一个代数方程，解方程再展开就得到通项。它的价值不在「更快」，在于把一个需要灵感的动作（找通项）换成一个按部就班的流程。
机制一条递推通过把数列装进幂级数变成一个可以按部就班解的代数方程。
可迁移性测试
换到信号处理：把一个时间序列做变换之后，卷积变成乘法，难算的操作变成好算的。不同构的地方在于信号处理必须关心收敛，而组合学里的形式幂级数不必——它只是数列的一种记法。
推导04
从递推到通项：以卡特兰数为例
这一段要证的是卡特兰数的递推与闭式，并显示每一步各自属于哪一类。
定义 为长度 的合法括号串个数，
定理前提。初值必须单独规定，递推本身不给出它。
每个非空合法串唯一分解为 ，其中 、 各自合法
定理前提，也是整条递推的全部内容：分解的唯一性保证不重不漏。
生成函数取形式幂级数，不讨论收敛
定理前提。这一条使后面的代数操作合法，无需分析上的条件。
推导 · 0 / 4
裂缝05
本章命题的边界
争议地形06
本书主张
递推与生成函数是解决计数问题的标准流程：先按某种方式分类得到递推，再用生成函数解出通项。
另一种看法
双射方法一线主张：闭式若能由一个显式双射直接得到，那个双射比生成函数的推导更有价值——卡特兰数的反射法证明就直接给出 ，同时解释了为什么会出现 这个因子。
分歧扎在
分歧扎在「解出来与解释清楚哪个优先」这一条上，而不在数学上。两条路线给出同一个闭式，争的是哪一种在遇到变体问题时更能改造。
什么证据能裁决
能裁决它的是变体问题上的表现：给两组学习者分别用生成函数与双射路线得到卡特兰数，然后给一道变体（如限制某种括号出现次数），比较解出率。若双射组明显更高，其主张成立。
目前的证据把天平压向「取决于变体的类型」：加线性约束时生成函数更顺手，加结构约束时双射更顺手。还差的是把变体类型事前分类的判据。
边界与反例07
把「按最后一步分类」的建模承诺写成可检验的规格
要检验的建模承诺是：现实中的递归结构存在唯一分解，因而按最后一步分类得到的递推不重不漏。
去掉哪条假设：分解唯一
递推不重不漏的全部依据；分解不唯一时同一个对象被数多次。
该情形下的具体反例：把一段流程按「最后一个环节」拆分，而某些流程的最后一个环节可以有两种识别方式
同一条流程因此进入两个类别，计数偏大。
这条承诺对应的可观测量：对同一批对象，独立执行分解规则得到的分类结果
必须是同一规则、同一批对象的独立执行。
什么观测算它不成立：同一对象被分入不同类别的比例超过事前登记的阈值
阈值按对象本身的边界模糊程度事前定死。
事前登记的失败条件：比例超阈值，或递推算出的总数与直接枚举结果差距超阈值
两者都按承诺不成立处理。
推导 · 0 / 3
接口08
挂在哪个槽位
挂在哪个槽位你已有的那条结论多半是「复杂问题拆成小问题」——一条关于分治的判断。本章要动的是它漏掉的那个条件。
本章对你已有的结构做的是 (a) 替换「拆成小问题」这条结论，还是 (b) 约束它：拆法必须对每个对象唯一，否则子问题的解加起来会重复？
慢变量登记两个慢变量：你手上有几处递归拆分核对过唯一性，以及有几处用小规模枚举验证过。三天后先看第二个。
小结09
本章小结
01递推来自「按最后一步分类」，换一个分类方式就换一条递推。
02递推只约束相邻项，初值必须单独规定，否则数列不确定。
03生成函数把递推变成代数方程，价值在于把找通项从灵感变成流程。
04组合学里的生成函数是形式幂级数，不必讨论收敛。
05唯一承担观测风险的是「现实中的分解唯一」，不是任何闭式。
提取练习 · 合上书，先自己答一遍。
?「卡特兰数的闭式」是 (a) 由递推与代数运算得到的 还是 (b) 关于现实的建模承诺？
?斐波那契递推在不同初值下给出不同数列，说明递推 (a) 不成立 还是 (b) 只约束相邻项？
受迫二选一10
A 机制辨识
下面哪一条是机制？
二选一
受迫二选一11
D 接口判断
哪一条能挂进你已有的结构？
二选一
读到这里，把它记为已读。