OGF · 乘积即卷积

生成函数：把序列装进多项式

计数得到的常常不是一个数，而是一整列数：规模取遍 $0, 1, 2, \dots$ 时方案数各是多少。把这一列数当作多项式的系数写下来，就得到它的生成函数（generating function）。数列的加法、卷积与移位从此都有对应的多项式运算，一条递推关系可以整体解成一个闭式。

1 · 数列与形式幂级数的对应

定义 1.1（普通生成函数） 数列 $a_0, a_1, a_2, \dots$ 的普通生成函数（ordinary generating function）是 $A(x) = \sum_{k \ge 0} a_k x^k$ ，记 $[x^k] A(x) = a_k$ 。

定义式里的 $A(x)$ 是形式幂级数（formal power series）： $x$ 不代入任何数值，收敛与否不参与运算，两个级数相等当且仅当逐项系数相等。加、减、乘按多项式的规则逐项做；常数项非零的级数还有乘法逆， $\frac{1}{1-x}$ 就是 $1-x$ 的逆，与 $|x| < 1$ 无关。

本系列已经见过两个生成函数。二项式定理说 $(1+x)^n$ 的系数就是组合数（见 Pascal 三角与二项式定理）；而 $(1-x)^n$ 的逆给出

\frac{1}{(1-x)^n} = \sum_{k \ge 0} \binom{n+k-1}{k} x^k

右边的系数是从 $n$ 个类型里可重复地取 $k$ 个的方案数（见可重复选取）。两条结论在此前各自成立，装进级数之后它们是同一个环里的一对互逆元素。

2 · 乘积与卷积

[xᵏ] A·B = Σⱼ aⱼ bₖ₋ⱼ

两个生成函数相乘，第 $k$ 项系数收集了所有次数配对成 $k$ 的项：

[x^k]\, A(x)B(x) = \sum_{j=0}^{k} a_j\, b_{k-j}

组合上的读法是：一个对象由两个互不干扰的部件拼成、规模相加，则整体的生成函数是两个部件生成函数的乘积。范德蒙德卷积就是这条规则在 $(1+x)^m (1+x)^n = (1+x)^{m+n}$ 上的一个实例，两边 $x^k$ 的系数对齐即得。

图 2-1 · 两个形式幂级数相乘后的系数数组。可切换左右因子与二项式指数

m

，单击乘积行的任一系数，看它由哪些配对相加而来。

警示 · 系数用 number 存，精度在溢出之前就已经丢了。本页测试拿 polyPow([1, 1], n)（全程整数加乘）与 combinatorics.ts 里的 comb 逐项对照：两者在 $n \le 55$ 上处处相等， $n = 56$ 的 $k = 23$ 处首次分歧，comb 给出 3167295784216201，累乘给出 3167295784216200，用 BigInt 复算确认后者为准。该值约 $3.2 \times 10^{15}$ ，仍在 Number.MAX_SAFE_INTEGER（约 $9.0 \times 10^{15}$ ）之内，失真来自 comb 递推里的中途除法而非溢出。本页测试的对照上界因此定在 $n = 55$ ，comb 未作改动。

3 · 递推关系的闭式解

Fibonacci 数列由 $F_0 = 0$ 、 $F_1 = 1$ 与 $F_n = F_{n-1} + F_{n-2}$ 定义。把递推式乘上 $x^n$ 对 $n \ge 2$ 求和，三个和式分别凑成 $F(x) - x$ 、 $xF(x)$ 与 $x^2 F(x)$ ，整理得

F(x) = \frac{x}{1 - x - x^2}

递推关系至此变成一个有理式。分母的两根决定部分分式分解，展开后得到 Binet 闭式 $F_n = (\varphi^n - \psi^n)/\sqrt{5}$ ，其中 $\varphi = (1+\sqrt{5})/2$ 、 $\psi = (1-\sqrt{5})/2$ 。同样的手法作用在 $C(x) = 1 + x\,C(x)^2$ 上，解一元二次方程即得 Catalan 数的 $C(x) = \frac{1 - \sqrt{1-4x}}{2x}$ 。

闭式看着比递推省事，浮点直算却比递推先坏。gf.ts 的 fibSeries 用形式幂级数求逆取系数，全程只有整数加法；fibClosed 按 Binet 用双精度直算。两者取整后在 $n \le 70$ 上处处相等， $n = 71$ 首次分歧：递推给 308061521170129，闭式给 308061521170130。而递推一路精确到 $n = 78$ ，直到 $F_{79} = 14472334024676221$ 超出 Number.MAX_SAFE_INTEGER 才错成结尾 220 的那个数。闭式提前八项失真，代价是无理数的开方与幂。

4 · 面额集合的连乘

∏ 1/(1−xᶜ) · 换钱方案数

一种面额 $c$ 可以用 0 枚、1 枚、2 枚……，它单独的生成函数是 $1 + x^c + x^{2c} + \dots = \frac{1}{1-x^c}$ 。各面额互不干扰，按 §2 的乘积规则，用面额集合凑出各金额的方案数就是连乘积

\prod_i \frac{1}{1 - x^{c_i}}

的系数序列。这个连乘不必真的展开成级数再取系数：逐个乘入因子时，每一步的系数数组恰好是完全背包一维实现的一轮更新——乘入 $\frac{1}{1-x^c}$ 等价于让 $v$ 从小到大做 $F[v] \mathrel{+}= F[v-c]$ （见完全背包）。生成函数与动态规划在此是同一份计算的两种记法。

图 4-1 · 面额逐个乘入后的系数数组，每一行比上一行多一个因子。可增删面额与调整金额上限，单击任一系数看它的两个来源。

面额 1、5、10、25、50 凑出 100 共 292 种方案；把 100 本身也算作一种面额则是 293 种。前一个数是换钱问题的经典答案，coinWays 与递归暴力枚举在 $0$ 到 $24$ 的全部金额上逐项核对过。

5 · 参考文献

Generating function. Wikipedia. 普通生成函数、指数型生成函数与常用变换表。https://en.wikipedia.org/wiki/Generating_function
Formal power series. Wikipedia. 形式幂级数环的运算规则与乘法逆的存在条件。https://en.wikipedia.org/wiki/Formal_power_series
Fibonacci sequence. Wikipedia. 生成函数 $x/(1-x-x^2)$ 与 Binet 闭式的推导。https://en.wikipedia.org/wiki/Fibonacci_sequence
Wilf, H. S. (2006). generatingfunctionology (3rd ed.). A K Peters. 生成函数方法的标准教材，从普通型讲到指数型与狄利克雷型。