生成函数原理与应用

可视化演示

生成函数将数列编码为形式幂级数，是组合计数的强大工具。本文详解普通生成函数与指数生成函数的定义、运算性质与卷积... 切换模式查看不同维度。

生成函数定义：给数列做“标签账本”

阿数贴标签的方法其实很有讲究。每张纸条上的数字就是“数列的一项”，而标签 \(x^n\) 上的指数 \(n\)，就是它在队伍里的位置。位置不同，标签就不同——第 3 天的纸条绝不能贴在第 1 天的位置上。

这种“给每一项贴上位置标签”的编码方式，就是生成函数的核心思想。把数列 \((a_0, a_1, a_2, \dots)\) 变成一串多项式：

这里的 \(x\) 是个“占位符”，数学家称这种不要求 \(x\) 取任何具体数值的级数为形式幂级数。它像名片上的印章：只用来区分身份，不用来兑换现金。正因为 \(x\) 不取值，无穷级数也不需要讨论“收敛不收敛”——我们只关心每张纸条上的系数 \(a_n\)。

举个例子：数列 \(1, 2, 4, 8, \dots\)（每天销量翻倍）的生成函数就是 \(1 + 2x + 4x^2 + 8x^3 + \cdots\)。把这个式子写出来，整家店的经营记录就全部装进了一串多项式里。

阿数把一抽屉纸条变成一串项链。这串项链不只是收纳工具，它还保留了每张纸条的位置信息——这正是生成函数后续能做加减乘除的基础。

普通生成函数：最朴素的记账法

阿数最常用的记账法就是“原样记录”——第 \(n\) 天的销量直接写在 \(x^n\) 的标签下，不加任何修饰。这种最直接的编码方式，就是普通生成函数（OGF）。

$$\displaystyle A(x) = \sum_{n=0}^{\infty} a_n x^n$$

它的威力体现在一个经典式子上：如果数列是 \(1, 1, 1, \dots\)（每天恰好卖 1 份招牌菜），那么它的 OGF 是：

$$\displaystyle \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$$

左边是无穷项，右边只有短短一行——数学家把这种“把无限长账单折叠成一行”的表达式叫做封闭形式。有了封闭形式，我们就能借用代数工具研究数列。而要从折叠的账本中取出某一天的销量，只需用系数提取符号：

$$\displaystyle [x^n] A(x) = a_n$$

记号 \([x^n]\) 读作“提取 \(x^n\) 的系数”，好比从账本里精准抽出第 \(n\) 张纸条。

1. 左侧 \(\sum x^n\)：无穷多个 1 依次排列，代表常数数列 \(1,1,1,\dots\)。

$$\displaystyle 1 + x + x^2 + x^3 + \cdots$$

2. 等号（折叠）：把无穷级数“卷”成一个简洁的分式，这是几何级数求和的本质。

$$\displaystyle \sum_{n=0}^{\infty} x^n = 1 + x + x^2 + \cdots = \frac{1}{1-x}$$

3. \(\frac{1}{1-x}\)：封闭形式。账本从无限长变成一行，搬家时轻松带走。

$$\displaystyle \frac{1}{1-x}$$

4. \([x^n]\) 符号：从封闭形式中反向展开，抽出第 \(n\) 项的系数。

$$\displaystyle [x^n]\frac{1}{1-x} = 1$$

阿数发现，账本折叠后好拿多了，要用系数时再展开，每张纸条一个不少。这就是普通生成函数：朴素，却极其好用。

指数生成函数：给排列“脱外套”的账本

有些菜要按顺序上——前菜、主菜、甜点，顺序不同就算不同的套餐。阿数发现普通账本会把“顺序”也算进去，可她有时只想统计“有哪些菜”而不管先后。于是她发明了第二种账本：每张纸条上盖一个“除以 \(n!\)”的章。

$$\displaystyle \widetilde{A}(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$$

这就是指数生成函数（EGF）。其中 \(n!\) 是 \(n\) 个元素的排列数。做一个“由 \(n\) 个不同元素组成的排列”时，内部有 \(n!\) 种顺序，除以 \(n!\) 就把顺序“抹平”了。EGF 最著名的封闭形式是：

$$\displaystyle \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x$$

因为 \(e^x\) 的泰勒展开正是这个级数。这解释了“指数生成函数”的名字由来。再看一个巧妙的例子：\(n\) 个元素的全排列数是 \(n!\)，它的 EGF 为：

$$\displaystyle \sum_{n=0}^{\infty} n! \cdot \frac{x^n}{n!} = \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$$

排列数 \(n!\) 被分母抵消后，露出了朴素的几何级数——这正是 EGF 的“脱外套”魔法。

1. 分子 \(a_n\)：数列本身，比如 \(n\) 个元素的全排列数 \(n!\)。

$$\displaystyle a_n = n!$$

2. 分母 \(n!\)：抹平内部顺序的“章”。盖了这个章，排列不再区分先后。

$$\displaystyle \frac{a_n}{n!}$$

3. \(e^x\) 级数：全 1 数列的 EGF 恰好是指数函数，这是 EGF 得名的由来。

$$\displaystyle \sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x$$

4. 抵消现象：当 \(a_n = n!\) 时，分子分母相约，露出普通几何级数。

$$\displaystyle n! \cdot \frac{x^n}{n!} = x^n$$

阿数把这本“盖章账本”挂在墙上，处理排列套餐时再也不被顺序干扰。她心里清楚：普通问题用 OGF，排列问题用 EGF。

运算性质：账本的合并、平移与微调

账本不只是存放的，还可以像实体账本一样操作。阿数常常把两本账并排相加，或者把一本账整体往后挪一天，再用放大镜观察每一天的变化率。这些操作在生成函数里都有对应：

$$\displaystyle A(x) \pm B(x) = \sum_{n=0}^{\infty} (a_n \pm b_n) x^n$$

加法就是逐项相加——两本账每天并起来，简单明了。而乘法更有意思，它生成了一个新的数列（卷积），我们下一节专门讲。再看两个“微调”技巧。移位：把整个数列右移 \(m\) 位，相当于在账本前面补 \(m\) 张空白纸条：

$$\displaystyle x^m A(x) = \sum_{n=m}^{\infty} a_{n-m} x^n$$

求导加权：对 \(A(x)\) 求导后乘回 \(x\)，相当于把第 \(n\) 天的销量放大 \(n\) 倍：

$$\displaystyle x A'(x) = \sum_{n=0}^{\infty} n\, a_n x^n$$

为什么求导会变成“放大 \(n\) 倍”？因为对 \(x^n\) 求导得到 \(n x^{n-1}\)，再乘回一个 \(x\)，指数恢复成 \(n\)，而系数多了一个因子 \(n\)。

1. 加法运算：对应数列逐项相加，是账本的“合并”。

$$\displaystyle a_n + b_n = [x^n]\big(A(x)+B(x)\big)$$

2. 乘法运算：对应卷积，新数列的每一项由旧项交叉相乘再求和。

$$\displaystyle [x^n]\big(A(x)B(x)\big) = \sum_{k=0}^{n} a_k b_{n-k}$$

3. 移位运算：乘 \(x^m\) 让整个数列右移，前面补零。

$$\displaystyle x^m A(x) = \sum_{n=m}^{\infty} a_{n-m} x^n$$

4. 求导加权：\(x A'(x)\) 把第 \(n\) 项的系数放大 \(n\) 倍。

$$\displaystyle n a_n = [x^n]\big(x A'(x)\big)$$

阿数像变魔术一样让账本平移、放大、合并。这些操作在解题时是她的“十八般兵器”。

卷积定理：套餐组合的计数魔法

这天阿数想让主菜师傅和甜点师傅联手推出“\(n\) 元套餐”：主菜花 \(k\) 元（有 \(a_k\) 种选择），甜点花 \(n-k\) 元（有 \(b_{n-k}\) 种选择），那么花恰好 \(n\) 元的套餐搭配数就是 \(a_k \cdot b_{n-k}\) 种。把所有可能的 \(k\) 累加，就得到卷积：

$$\displaystyle c_n = \sum_{k=0}^{n} a_k b_{n-k}$$

这正是两个生成函数相乘时，\(x^n\) 项的系数。换句话说：生成函数的乘法自动完成卷积。这是生成函数最神奇的地方——复杂的选择计数，变成了一次多项式乘法。

EGF 的卷积略有不同，会带上二项式系数：

$$\displaystyle c_n = \sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}$$

原因藏在指数运算里：\(\frac{x^k}{k!} \cdot \frac{x^{n-k}}{(n-k)!} = \binom{n}{k} \frac{x^n}{n!}\)。两个 EGF 相乘时，\(x^n/n!\) 的系数自动混入组合数 \(\binom{n}{k}\)，这正好对应“先从 \(n\) 个位置里选 \(k\) 个放第一种结构”的计数逻辑。

经典例子：掷两枚骰子，求点数之和的分布。单枚骰子的分布是 \(d = [\frac16, \frac16, \dots, \frac16]\)（6 个面），两枚点数之和的分布就是 \(d * d\) 的卷积。和为 7 的概率是 \(\frac{6}{36} = \frac{1}{6}\)。

1. \(a_k b_{n-k}\)：主菜花 \(k\) 元与甜点花 \(n-k\) 元的搭配数，两者相乘。

$$\displaystyle a_k \cdot b_{n-k}$$

2. 求和 \(\sum_{k=0}^{n}\)：把所有可能的 \(k\) 全部加起来，覆盖所有分钱方案。

$$\displaystyle \sum_{k=0}^{n} a_k b_{n-k}$$

3. 二项式系数 \(\binom{n}{k}\)：EGF 卷积里自带的“选位置”因子，来自两个阶乘分母的合并。

$$\displaystyle \frac{x^k}{k!} \cdot \frac{x^{n-k}}{(n-k)!} = \binom{n}{k}\frac{x^n}{n!}$$

4. 多项式乘法等价：\(A(x)B(x)\) 展开后，\(x^n\) 的系数就是 \(c_n\)。

$$\displaystyle [x^n]\big(A(x)B(x)\big) = c_n$$

主厨和甜点师的合作，就是生成函数乘法背后的秘密。阿数从此再也不用手工枚举套餐，一次乘法全搞定。

递推求解：从账本反推经营规律

阿数发现店里最近的销量有个规律：今天的销量等于昨天加前天的销量（老顾客总带着新顾客来）。她想知道第 100 天能卖多少，总不能一天天推下去。生成函数可以直接“解”出通项公式。这个经典问题就是斐波那契数列：

$$\displaystyle F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0,\ F_1 = 1$$

设 \(F(x) = \sum F_n x^n\) 为斐波那契数列的生成函数。利用移位公式，把递推式翻译成方程：

$$\displaystyle F(x) = x + xF(x) + x^2 F(x)$$

解得封闭形式：

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

接下来用部分分式把分母拆成两个一次因子。设 \(\varphi = \frac{1+\sqrt5}{2}\)，\(\psi = \frac{1-\sqrt5}{2}\)，则：

$$\displaystyle F(x) = \frac{1}{\sqrt{5}}\left(\frac{1}{1-\varphi x} - \frac{1}{1-\psi x}\right)$$

两边分别展开成几何级数，提取 \(x^n\) 系数，得到著名的比内公式：

$$\displaystyle F_n = \frac{1}{\sqrt{5}}\left(\varphi^n - \psi^n\right)$$

有了这条通项公式，阿数直接代入 \(n=100\) 就能算出第一百天的销量，不用再一天天递推。

1. 设生成函数：把整条递推数列编码成一个未知函数 \(F(x)\)。

$$\displaystyle F(x)=\sum_{n=0}^{\infty} F_n x^n$$

2. 代入递推：\(F_{n-1}\) 对应 \(xF(x)\)，\(F_{n-2}\) 对应 \(x^2F(x)\)，初值 \(F_1=1\) 产生单独的 \(x\)。

$$\displaystyle F(x) = x + xF(x) + x^2F(x)$$

3. 解方程：把含 \(F(x)\) 的项移到一边，提取公因式。

$$\displaystyle F(x)(1-x-x^2) = x$$

4. 部分分式：把分式拆成两个简单分式之差，每个都是几何级数的封闭形式。

$$\displaystyle \frac{x}{1-x-x^2} = \frac{1}{\sqrt{5}}\left(\frac{1}{1-\varphi x} - \frac{1}{1-\psi x}\right)$$

5. 提取通项：两个几何级数同时展开，\(x^n\) 的系数合并成比内公式。

$$\displaystyle F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}$$

阿数再也不用一天天数销量了。她把递推问题变成代数方程，一条公式直接算到第一百天。

分组与分配：把食材装进餐盒

阿数要把 \(n\) 个相同的包子打包出售，每份随便装几个，问有多少种打包方式。这就是整数拆分：把 \(n\) 写成若干正整数之和，顺序无关。比如 \(4\) 有 5 种拆分：\(4,\ 3+1,\ 2+2,\ 2+1+1,\ 1+1+1+1\)。

整数拆分的生成函数是一个无穷连乘：

$$\displaystyle \sum_{n=0}^{\infty} p(n) x^n = \prod_{k=1}^{\infty} \frac{1}{1-x^k}$$

理解这个式子的关键在于每个因子。因子 \(\frac{1}{1-x^k} = 1 + x^k + x^{2k} + \cdots\) 表示“选 0 份、1 份、2 份……重量为 \(k\) 的食材包”。把所有 \(k\) 的因子连乘，展开后 \(x^n\) 的系数就是总重量恰好为 \(n\) 的分装方案数 \(p(n)\)。

如果换成不同的物品（比如把 \(n\) 道不同的菜分给若干顾客），问题性质就变了——物品内部有顺序，这时要用 EGF。集合划分问题（把 \(n\) 个不同元素分成若干组）的 EGF 是著名的 Bell 数公式：

$$\displaystyle B(x) = e^{e^x - 1}$$

展开后 \(x^n/n!\) 的系数就是第 \(n\) 个 Bell 数，表示把 \(n\) 个不同元素分到任意多非空集合的方案数。

1. 因子 \(\frac{1}{1-x^k}\)：一种“单位重量 \(k\)”的食材包，选 \(j\) 个就贡献 \(x^{jk}\)。

$$\displaystyle \frac{1}{1-x^k} = 1 + x^k + x^{2k} + \cdots$$

2. 连乘 \(\prod\)：所有重量单位自由组合，最终覆盖所有拆分方案。

$$\displaystyle \prod_{k=1}^{\infty} \frac{1}{1-x^k}$$

3. 系数 \(p(n)\)：展开后 \(x^n\) 的系数，就是 \(n\) 的拆分方案数。

$$\displaystyle p(n) = [x^n]\prod_{k=1}^{\infty}\frac{1}{1-x^k}$$

4. EGF 分组：\(e^{e^x-1}\) 展开得到 Bell 数，适合处理“不同元素分到若干组”。

$$\displaystyle B(x) = e^{e^x-1} = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!}$$

阿数把“打包”问题变成了“选因子”问题。每种食材包自由组合，展开一算，方案数清清楚楚。

算法应用：从手工账本到计算机流水线

店越开越大，手工翻账本太慢，阿数把账本交给了计算机。生成函数在计算机里的化身是多项式，而多项式乘法就是卷积。朴素的多项式乘法要两两相乘，复杂度是 \(O(n^2)\)；但快速傅里叶变换（FFT）可以在 \(O(n\log n)\) 时间内完成卷积，这是信号处理、图像识别和 AI 推理的底层加速器。

另一个重要应用是概率母函数。设随机变量 \(X\) 取值非负整数，它的概率母函数定义为：

$$\displaystyle G(z) = \sum_{k=0}^{\infty} P(X=k)\, z^k$$

把每个概率值 \(P(X=k)\) 当作系数“挂”在 \(z^k\) 标签上。概率母函数最实用的性质是：对 \(z\) 求导后令 \(z=1\)，得到期望：

$$\displaystyle G'(1) = \mathbb{E}[X]$$

同理，二阶导数还能给出方差。这在分析随机算法的平均复杂度时极其有用。此外，生成函数还能解决背包计数问题：把每个物品的重量 \(w\) 编码成因子 \((1 + x^w)\)（选或不选），所有因子连乘后，\(x^n\) 的系数就是凑出总重量 \(n\) 的方案数。

1. \(\sum P(X=k)z^k\)：把每个概率值当作系数，随机变量的分布被编码成一个幂级数。

$$\displaystyle G(z)=\sum_{k=0}^{\infty}P(X=k)\,z^k$$

2. \(G'(1)\)：对 \(z\) 求导后令 \(z=1\)，正好是期望 \(\mathbb{E}[X]\)。

$$\displaystyle G'(1)=\mathbb{E}[X]$$

3. FFT 加速：快速傅里叶变换把卷积从 \(O(n^2)\) 降到 \(O(n\log n)\)。

$$\displaystyle \text{FFT: } O(n^2) \to O(n\log n)$$

有了计算机流水线，阿数再大的账本也能瞬间算完。从数学公式到高效代码，生成函数一直是那本万能的“标签账本”。

AI 应用场景

Python 演示

import sympy as sp x = sp.symbols('x')  def extract(expr, n_max):    """展开生成函数并提取前 n_max+1 个系数"""    s = sp.series(expr, x, 0, n_max + 1).removeO()    return [s.coeff(x, k) for k in range(n_max + 1)]  def main():    # 1) 斐波那契 生成函数 vs 递推    F = x / (1 - x - x**2)    gf = extract(F, 10)    fib = [0, 1]    for _ in range(9):        fib.append(fib[-1] + fib[-2])    print('生成函数系数:', gf)    print('递推前10项 :', fib[:10])    assert gf == fib[:10], '两种方法结果不一致'     # 2) 整数拆分 p(n) = [x^n] prod 1/(1-x^k)    P = sp.prod(1 / (1 - x**k) for k in range(1, 6))    ps = sp.series(P, x, 0, 11).removeO()    p = [ps.coeff(x, k) for k in range(11)]    print('整数拆分 p(0)~p(10):', p)     # 3) 两枚骰子点数之和的卷积    die = [1 / 6] * 6    prob = [0] * 13    for i in range(6):        for j in range(6):            prob[i + j + 2] += die[i] * die[j]    print('和为7的概率:', prob[7])  if __name__ == '__main__':    main()

1. F = x / (1 - x - x**2)斐波那契数列的生成函数，用封闭形式代替无穷级数。
2. gf = extract(F, 10)把生成函数展开成幂级数，逐项取出前 10 个系数。
3. assert gf == fib[:10]用递推暴力算出的结果做对照，保证生成函数解正确。
4. P = sp.prod(1 / (1 - x**k) for k in range(1, 6))整数拆分的“连乘账本”，每个因子代表一种单位重量的食材包。
5. ps = sp.series(P, x, 0, 11).removeO()展开连乘积并丢弃高阶余项，只保留前 11 项。
6. prob[i + j + 2] += die[i] * die[j]卷积的核心操作：两枚骰子的点数相加，概率累加。

常见误区

面试题