6.3 生成函数：把计数序列编码成代数对象
补给方案的种类随着数量增长迅速失控，塔里的计数师把整列答案编码进一个幂级数。
当计数条件包含“每类可选若干个”“总数量恰好为 n”“多种组件组合”，逐项列举很快变乱。生成函数把一个序列放进幂级数的系数，使选择的组合变成多项式乘法。
普通生成函数
序列：
a₀,a₁,a₂,...的普通生成函数（OGF）：
A(x)=Σ_{n≥0} a_n x^nx 主要是记录规模的形式变量，[x^n]A(x) 表示 x^n 的系数：
a_n=[x^n]A(x)生成函数不是把序列值拿去逐个求函数值；它把整列系数打包，允许用代数运算操纵计数。
选择数量怎样变成多项式
一种组件可选 0、1、2 个：
1+x+x²另一种可选 0 或 3 个：
1+x³同时选择两类时相乘：
(1+x+x²)(1+x³)
=1+x+x²+x³+x⁴+x⁵2
x⁴ 的系数为 1，表示总数为 4 有一种组合：第一类 1 个、第二类 3 个。
若不同来源能以多种方式贡献同一总数，乘法展开后同次幂系数会相加，自动完成计数。
无限几何级数
某类对象可选任意非负个：
1+x+x²+...=1/(1-x)作为形式幂级数，这个恒等式来自：
(1-x)(1+x+x²+...)=1若有 k 类对象，每类可选任意个：
1/(1-x)^k其 x^n 系数是：
C(n+k-1,k-1)这与隔板法得到的重组合公式一致。
硬币找零的生成函数
硬币面额 1,2,5，每种可用任意枚，按枚数组合且不计顺序：
G(x)=1/[(1-x)(1-x²)(1-x⁵)][x^n]G(x) 是凑成金额 n 的组合数。
若每种硬币最多一枚：
(1+x)(1+x²)(1+x⁵)若 2 元硬币最多三枚：
1+x²+x⁴+x⁶生成函数的每个因子直接表达局部选择限制。
注意：这里不计硬币排列顺序。若把 1+2 与 2+1 看作不同序列，需要另一种模型。
用生成函数解 Fibonacci 递推
定义：
F₀=0, F₁=1
Fₙ=Fₙ₋₁+Fₙ₋₂2
令：
F(x)=Σ_{n≥0}Fₙxⁿ对 n≥2 的递推乘 xⁿ 并求和：
F(x)-x = xF(x)+x²F(x)所以：
F(x)=x/(1-x-x²)对分母因式分解并做部分分式展开，可以恢复 Binet 公式。生成函数把递推关系转成代数方程，这是它在组合数学中的核心用途之一。
卷积对应独立规模的组合
若：
A(x)=Σa_nx^n
B(x)=Σb_nx^n2
则：
[x^n]A(x)B(x)=Σ_{k=0..n} a_k b_{n-k}右边是离散卷积：把总规模 n 拆成 k 和 n-k，分别选择 A 类结构和 B 类结构。
解析树计数、括号结构、字符串拼接和动态规划中都能看到这种拆分。算法里的卷积还可用 FFT 等方法加速，但数值误差和模数选择属于后续主题。
指数生成函数何时出现
若对象带标签，普通生成函数常不能直接处理标签分配。指数生成函数（EGF）写作：
A(x)=Σ a_n x^n/n!它适合排列、带标签结构和集合分拆等问题。OGF 与 EGF 的乘法规则编码不同的组合操作，不能因为名字相似混用。
本课只建立区分：
- OGF 常用于按大小计数的无标签组合；
- EGF 常用于带标签对象；
- 具体使用由组合类结构决定，不是看到阶乘就机械选择。
软件中的状态计数
生成函数适合约束配置总量。例如 10 个插件中：
- 每个基础插件可选或不选：因子
(1+x)； - 某类插件最多选 2 个：因子
1+x+x²； - 每个插件还有不同权重，可让指数记录成本而非个数。
但软件状态常存在依赖和互斥，不能把每个选项因子盲目相乘。若插件 B 依赖 A，可以：
- 分类为“不选 A，也不能选 B”与“选 A，再决定 B”；
- 构造有限状态自动机并使用转移矩阵；
- 使用 SAT/SMT 或 BDD 统计满足赋值。
计数结果还可能把行为等价的配置重复计算。若要按对称性取商，需要群作用与 Burnside 引理等更高级工具。
从规模到测试策略
知道状态数巨大，只能证明穷举不现实。接下来还要：
- 找出约束后的可达状态；
- 按风险选择边界和代表类；
- 用组合覆盖测试覆盖 t 路交互；
- 用属性测试生成并缩小反例；
- 对关键有限模型使用求解器或模型检查。
Pairwise 覆盖保证每对参数值至少共同出现一次，不保证发现所有三方或更高阶交互错误，也不证明系统正确。
完成检查
- 写出每种最多 3 个、共 4 种组件的 OGF；
- 求总共选择 5 个组件的方案数；
- 为面额 1、3、4 的硬币写出无限供应生成函数；
- 推导递推
a_n=2a_{n-1}+1的生成函数； - 为一个带依赖的插件配置解释为什么简单乘法会多算非法状态。