6.3 生成函数：把计数序列编码成代数对象

当计数条件包含“每类可选若干个”“总数量恰好为 n”“多种组件组合”，逐项列举很快变乱。生成函数把一个序列放进幂级数的系数，使选择的组合变成多项式乘法。

普通生成函数

序列：

a₀,a₁,a₂,...

的普通生成函数（OGF）：

A(x)=Σ_{n≥0} a_n x^n

x 主要是记录规模的形式变量，[x^n]A(x) 表示 x^n 的系数：

a_n=[x^n]A(x)

生成函数不是把序列值拿去逐个求函数值；它把整列系数打包，允许用代数运算操纵计数。

形式幂级数运算按系数定义：求乘积的第 n 项只需要有限多个系数，所以这里不用给 x 一个数值，也不要求级数收敛。若改成数值函数讨论，几何级数等式才需要例如 |x|<1 这样的收敛条件。

选择数量怎样变成多项式

一种组件可选 0、1、2 个：

1+x+x²

另一种可选 0 或 3 个：

1+x³

同时选择两类时相乘：

(1+x+x²)(1+x³)
=1+x+x²+x³+x⁴+x⁵

x⁴ 的系数为 1，表示总数为 4 有一种组合：第一类 1 个、第二类 3 个。

若不同来源能以多种方式贡献同一总数，乘法展开后同次幂系数会相加，自动完成计数。

无限几何级数

某类对象可选任意非负个：

1+x+x²+...=1/(1-x)

作为形式幂级数，这个恒等式来自：

(1-x)(1+x+x²+...)=1

若有 k≥1 类对象，每类可选任意个：

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 看作不同序列，需要另一种模型。

下面用 Python 3 逐个乘入无限硬币因子，只保留到目标金额的系数。输入为有限、无重复的正整数面额序列与非负整数金额：

def coin_combinations(coins, target):
    if target < 0 or any(c <= 0 for c in coins) or len(set(coins)) != len(coins):
        raise ValueError("distinct positive denominations and nonnegative target required")
    ways = [0] * (target + 1)
    ways[0] = 1
    for coin in coins:
        for total in range(coin, target + 1):
            ways[total] += ways[total - coin]
    return ways

print(coin_combinations((1, 2, 5), 5))  # [1, 1, 2, 2, 3, 4]
print(coin_combinations((), 0))         # [1]

外层按面额处理、内层金额递增，使 ways[total-coin] 已允许继续使用当前面额，正好对应无限供应。处理完一种面额，数组表示已经纳入的那些因子的乘积。若改成金额在外层、逐币累加，就会计数有序序列，金额 5 会得到 9 而不是 4。

用生成函数解 Fibonacci 递推

定义：

F₀=0, F₁=1
Fₙ=Fₙ₋₁+Fₙ₋₂, n≥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^n

则：

[x^n]A(x)B(x)=Σ_{k=0..n} a_k b_{n-k}

右边是离散卷积：把总规模 n 拆成 k 和 n-k，分别选择 A 类结构和 B 类结构。

小规模系数可以直接用整数卷积。下面每类最多选 3 个，共 4 类，求总量 5 的组合数；次数超过 5 的项不会再影响低次系数，因此每次都可截断：

def multiply_truncated(a, b, limit):
    result = [0] * (limit + 1)
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            if i + j <= limit:
                result[i + j] += x * y
    return result

coefficients = [1]
for _ in range(4):
    coefficients = multiply_truncated(coefficients, [1, 1, 1, 1], 5)
print(coefficients[5])  # 40: [x^5](1+x+x²+x³)^4

解析树计数、括号结构、字符串拼接和动态规划中都能看到这种拆分。算法里的卷积还可用 FFT 等方法加速，但数值误差和模数选择属于后续主题。

指数生成函数何时出现

若对象带标签，普通生成函数常不能直接处理标签分配。指数生成函数（EGF）写作：

A(x)=Σ a_n x^n/n!

它适合排列、带标签结构和集合分拆等问题。OGF 与 EGF 的乘法规则编码不同的组合操作，不能因为名字相似混用。

若 A,B 是 EGF，乘积对应的计数是 c_n=Σ_{k=0..n} C(n,k)a_kb_{n-k}。额外的 C(n,k) 负责从 n 个不同标签中选出给 A 部分的 k 个。例如两部分每个标签集各只有一种结构时，总数为 Σ C(n,k)=2^n，而普通系数卷积只会给 n+1。

本课只建立区分：

• OGF 常用于按大小计数的无标签组合；
• EGF 常用于带标签对象；
• 具体使用由组合类结构决定，不是看到阶乘就机械选择。

软件中的状态计数

生成函数适合约束配置总量。例如对 10 个身份不同的可选插件：

• 每个插件可选或不选：各贡献 (1+x)，总生成函数 (1+x)^10；
• 若这 10 个插件总共最多选 2 个，截断后为 1+10x+45x²；
• 每个插件还有不同权重，可让指数记录成本而非个数。

1+x+x² 只适用于“每个数量各一种方式”的模型，例如一种不可区分组件可取 0、1、2 个。插件身份不同，选择一个就有 10 种，不能把这些系数省掉。对仅有 A、B 且 B 依赖 A 的系统，合法子集是 ∅,{A},{A,B}，生成函数恰好是 1+x+x²；相同多项式可以来自不同对象模型。

但软件状态常存在依赖和互斥，不能把每个选项因子盲目相乘。若插件 B 依赖 A，可以：

• 分类为“不选 A，也不能选 B”与“选 A，再决定 B”；
• 构造有限状态自动机并使用转移矩阵；
• 使用 SAT/SMT 或 BDD 统计满足赋值。

计数结果还可能把行为等价的配置重复计算。若要按对称性取商，需要群作用与 Burnside 引理等更高级工具。

从规模到测试策略

判断穷举是否可行，还要结合状态数量、每次检查成本与资源预算。接下来还要：

• 找出约束后的可达状态；
• 按风险选择边界和代表类；
• 用组合覆盖测试覆盖 t 路交互；
• 用属性测试生成并缩小反例；
• 对关键有限模型使用求解器或模型检查。

在带约束的模型中，pairwise 覆盖 要求每个可扩展为合法配置的参数值对至少共同出现一次。它是 t=2 的组合覆盖，不保证发现三方或更高阶交互错误，也不证明系统正确。

完成检查

1. 写出每种最多 3 个、共 4 种组件的 OGF；
2. 求总共选择 5 个组件的方案数；
3. 为面额 1、3、4 的硬币写出无限供应生成函数；
4. 推导递推 a_n=2a_{n-1}+1 的生成函数；
5. 为一个带依赖的插件配置解释为什么简单乘法会多算非法状态。

参考资料

• MIT Mathematics for Computer Science
• generatingfunctionology