生成函数

这一页教你把一整条计数数列 $a_0,a_1,a_2,\dots$ 编码进一个幂级数 $G(x)$，然后用代数运算代替组合推理。学完之后，你能处理两类原本很绕的问题：带约束的选取计数（“苹果必须偶数个、香蕉至少一个”这类条件），以及求递推数列的通项公式。核心只有一句话：乘法就是分步计数，系数提取就是答案。

从一个念头开始

第 3 章的组合计数处理的是干净问题：无重复选取、恰好 $k$ 个。现实里的计数问题总带着附加条件——每类物品的数量上限下限不同、总数不固定。条件一多，分类讨论很快就失控。

有一个想法可以避开这一切：与其逐个计算 $a_n$，不如把整条数列当作一个对象来研究。把 $a_n$ 挂在 $x^n$ 上做成幂级数，“恰好选 $n$ 个”就变成了”$x^n$ 的系数”。约束条件则用级数的形状表达：只许偶数个，对应 $1+x^2+x^4+\cdots$；至少一个，对应 $x+x^2+x^3+\cdots$。分步选择对应乘法，互斥情形对应加法——第 3 章的加法原理和乘法原理在这里升级成级数的加法和乘法。计数问题于是变成代数问题：因式分解、展开、读系数。

普通生成函数

数列 $a_0,a_1,a_2,\dots$ 的普通生成函数（ordinary generating function, OGF）是幂级数

$$G(x)=\sum _{n\ge 0}{a}_n{x}^n=a_0+a_{1}x+a_2{x}^2+\cdots .$$

例如常数列 $1,1,1,\dots$ 的生成函数是 $1+x+x^2+\cdots$，等比数列 $1,2,4,8,\dots$ 的生成函数是 $1+2x+4x^2+\cdots$。我们把 $G(x)$ 看作数列的一种”封装”，$x$ 是占位符而非未知数。

这里要立下一句话的规矩：本节把幂级数当作形式幂级数处理——只关心系数序列和系数的代数运算，不问 $x$ 取什么值时级数收敛。收敛半径是分析学的课题，组合推理里完全不需要它。所有”令 $|x|$ 足够小”的写法都只是习惯口头禅，你可以直接无视。

基本运算与它们的组合含义

每种代数运算都有一个组合解释，这是生成函数好用的根本原因。

加法。 $(G+H)(x)$ 的系数是 $a_n+b_n$，对应互斥的两类方案做并集——正是加法原理。

乘法（卷积）。 设 $A(x)=\sum a_n{x}^n$，$B(x)=\sum b_n{x}^n$，则

$$A(x)B(x)=\sum _{n\ge 0}\left(\sum _{k=0}^n{a}_k{b}_{n-k}\right)x^n.$$

内层那个和叫卷积。组合含义：完成一件事要分两步，第一步规模 $k$ 有 $a_k$ 种做法，第二步规模 $n-k$ 有 $b_{n-k}$ 种做法，对所有可能的 $k$ 求和，就是”两步合计 $n$ 个”的总方案数——乘法原理对所有分割方式的累加。这一条是全章的引擎。

移位与乘以 $x$。 $xG(x)={\sum }_{n\ge 0}{a}_n{x}^{n+1}={\sum }_{m\ge 1}{a}_{m-1}{x}^m$，即整条数列下标加一、首项变零。组合上，“先固定垫一个，再从 $n-1$ 个里选”对应的正是因子 $x$——所以约束”至少一个”由因子 $x+x^2+\cdots =\frac{x}{1-x}$ 表达。同理 $G(x)-a_0$ 是删掉首项。

求导与积分。 $G^{\prime }(x)$ 的系数是 $(n+1)a_{n+1}$；反过来积分把系数除以序号。一个有用的组合是 $x{G}^{\prime }(x)={\sum }_{n\ge 0}n{a}_n{x}^n$，即”带权计数”——每个方案按规模 $n$ 加权。求导能把”$n$ 倍”这类权重搬进系数里，处理期望值相关的问题时会用到。

部分分式。 拿到有理函数形式的生成函数后，标准的拆项技术叫部分分式分解：把它拆成若干个 $\frac{c}{1-ax}$ 之和，每一项都认识。这是已知技术，本节只使用不展开。

常用级数库

下面五个级数是工具箱的常备件，系数提取全靠认出它们。

$$\frac{1}{1-x}=\sum _{n\ge 0}{x}^n,\frac{1}{1-ax}=\sum _{n\ge 0}{a}^n{x}^n,$$ $$(1+x{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k,\frac{1}{(1-x{)}^k}=\sum _{n\ge 0}(\genfrac{}{}{0ex}{}{n+k-1}{k-1})x^n.$$

第一个是几何级数，第二个把 $x$ 换成 $ax$。第三个是二项式定理，$n$ 为正整数时右边是有限多项式——它编码的是”从 $n$ 个不同元素任选”的计数（$x^k$ 的系数就是 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$）。第四个值得多看一眼：把左边写成 $k$ 个几何级数的乘积

$$\frac{1}{(1-x{)}^k}=\underset{k\text{ 个括号}}{\underbrace{(1+x+x^2+\cdots )(1+x+x^2+\cdots )\cdots (1+x+x^2+\cdots )}},$$

$x^n$ 的系数是”从 $k$ 个括号各取一个非负幂次、指数之和为 $n$“的取法数，也就是不定方程 $y_1+y_2+\cdots +y_k=n$ 的非负整数解个数——这正是第 3 章隔板法的结论 $\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$。隔板法在这里获得了一个新身份：它不是什么独立技巧，只是 $\frac{1}{(1-x{)}^k}$ 的系数。

第四个级数的常见变体：$\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$ 与 $\left(\genfrac{}{}{0ex}{}{n+k-1}{n}\right)$ 相等，两种写法都在用，提取系数时哪个顺手用哪个。

应用一：带约束的选取计数

例题 1. 一只水果篮装苹果、香蕉、梨三种水果，要求苹果装偶数个（可以零个）、香蕉至少一个、梨至多两个。设恰好装 $n$ 个水果的装法数为 $a_n$，求 $a_n$ 的生成函数，并算出 $a_4$。

解. 逐类写出数量约束对应的级数：

• 苹果偶数个：$1+x^2+x^4+\cdots =\frac{1}{1-x^2}$；
• 香蕉至少一个：$x+x^2+x^3+\cdots =\frac{x}{1-x}$；
• 梨至多两个：$1+x+x^2$（有限多项式，上限约束直接截断）。

分步选择对应乘法，所以

$$G(x)=\frac{1}{1-x^2}\cdot \frac{x}{1-x}\cdot (1+x+x^2).$$

求 $a_4$ 只需把乘积算到 $x^4$。先乘前两个因子：

$$\frac{1}{1-x^2}\cdot \frac{x}{1-x}=(1+x^2+x^4+\cdots )(x+x^2+x^3+x^4+\cdots )=x+x^2+2x^3+2x^4+O(x^5),$$

其中 $2x^3$ 来自 $1\cdot x^3+x^2\cdot x$，$2x^4$ 来自 $1\cdot x^4+x^2\cdot x^2$。再乘 $(1+x+x^2)$，$x^4$ 的系数是

$$a_4=2+2+1=5,$$

即前因子中 $x^4,x^3,x^2$ 的系数分别乘 $1,x,x^2$ 后相加。直接枚举验证：苹果 0 个时梨取 $0,1,2$ 对应香蕉 $4,3,2$，有 3 种；苹果 2 个时梨取 $0,1$ 对应香蕉 $2,1$，有 2 种；苹果 4 个时香蕉至少一个无法满足。合计 $3+2=5$，与系数一致。$■$

这个例子的方法论值得记住：每类物品写一个因子（下限用 $x$ 的幂垫位，上限截断，“恰好一类”用二项式），约束全部进因子之后，剩下的只是机械地乘开读系数。

应用二：用生成函数解递推

第 6 章用特征方程解常系数线性递推。生成函数给出同一条路的另一种走法，而且全程只做代数，不需要猜解的形式。流程固定三步：代入幂级数 → 解出 $G(x)$ 的代数方程 → 展开回系数。

例题 2. 解递推 $a_n=3a_{n-1}(n\ge 1)$，初值 $a_0=2$。

解. 设 $G(x)={\sum }_{n\ge 0}{a}_n{x}^n$。把递推两边从 $n=1$ 起乘 $x^n$ 再求和：

$$\sum _{n\ge 1}{a}_n{x}^n=3\sum _{n\ge 1}{a}_{n-1}{x}^n.$$

左边是 $G(x)-a_0=G(x)-2$；右边提出一个 $x$，余下的是完整的 $G(x)$，即 $3xG(x)$。于是

$$G(x)-2=3xG(x)⟹G(x)=\frac{2}{1-3x}.$$

认出 $\frac{1}{1-3x}={\sum }_{n\ge 0}{3}^n{x}^n$（级数库第二条，$a=3$），乘上分子 2 得

$$G(x)=\sum _{n\ge 0}2\cdot 3^n{x}^n⟹a_n=2\cdot 3^n.$$

迭代验证：$a_1=6,a_2=18,\dots$，与 $a_n=2\cdot 3^n$ 吻合。当然这个递推太简单，直接迭代就能猜出答案；生成函数真正的威力在下一步。$■$

例题 3. 用生成函数求斐波那契数列的通项：$F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}(n\ge 2)$。

解. 三步走完。

第一步：代入。 设 $G(x)={\sum }_{n\ge 0}{F}_n{x}^n$。把递推从 $n=2$ 起乘 $x^n$ 求和：

$$\sum _{n\ge 2}{F}_n{x}^n=\sum _{n\ge 2}{F}_{n-1}{x}^n+\sum _{n\ge 2}{F}_{n-2}{x}^n.$$

左边 $=G(x)-F_0-F_{1}x=G(x)-x$。右边第一项提出 $x$ 后下标平移，是 $x(G(x)-F_0)=xG(x)$；第二项提出 $x^2$，是 $x^{2}G(x)$。

第二步：解代数方程。

$$G(x)-x=xG(x)+x^{2}G(x)⟹G(x)=\frac{x}{1-x-x^2}.$$

第三步：展开回系数。 分母因式分解。令

$$\phi =\frac{1+\sqrt{5}}{2},\psi =\frac{1-\sqrt{5}}{2},$$

则 $\phi +\psi =1$，$\phi \psi =-1$，所以 $1-x-x^2=(1-\phi x)(1-\psi x)$。部分分式分解给出

$$\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\cdot \frac{1}{1-\phi x}-\frac{1}{\sqrt{5}}\cdot \frac{1}{1-\psi x}.$$

（求待定系数：设 $\frac{x}{(1-\phi x)(1-\psi x)}=\frac{A}{1-\phi x}+\frac{B}{1-\psi x}$，通分后比较常数项得 $A+B=0$，比较 $x$ 项得 $-A\psi -B\phi =1$，解出 $A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}}$。）

对两项分别用级数库第二条展开：

$$G(x)=\frac{1}{\sqrt{5}}\sum _{n\ge 0}{\phi }^n{x}^n-\frac{1}{\sqrt{5}}\sum _{n\ge 0}{\psi }^n{x}^n.$$

读系数，得到比内公式（Binet’s formula）：

$$F_n=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right].$$

验算：$n=1$ 时 $\frac{1}{\sqrt{5}}(\phi -\psi )=\frac{1}{\sqrt{5}}\cdot \sqrt{5}=1$；$n=2$ 时 $\frac{1}{\sqrt{5}}({\phi }^2-{\psi }^2)=\frac{1}{\sqrt{5}}(\phi -\psi )(\phi +\psi )=1$。由于 $|\psi |<1$，${\psi }^n$ 指数衰减，$F_n$ 是离 ${\phi }^n/\sqrt{5}$ 最近的整数——无理数组合出整数列，这正是生成函数方法的标志性画面。$■$

对比第 6 章的特征方程做法：猜 $F_n=r^n$、解 $r^2=r+1$、用初值定常数。两条路在代数上是同构的，特征方程的根 $\phi ,\psi$ 正是分母 $1-x-x^2$ 的根的倒数。生成函数的优势在于不用猜——幂级数代入是机械步骤，且它统一处理计数与递推两类问题。

指数生成函数：一句话定位

指数生成函数（EGF）把数列除以阶乘再封装：$\hat{G}(x)={\sum }_{n\ge 0}{a}_n\frac{x^n}{n!}$。它的乘法对应带二项式权重的卷积 ${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)a_k{b}_{n-k}$，组合含义是”把 $n$ 个带标号的元素拆成两组、分别计数再合并”——处理排列、错位重排这类标号问题时，EGF 是正确工具，本章不展开。

常见错误

在收敛性上卡住。 反复问”$x$ 取多少这个级数才收敛”是初学者最大的时间黑洞。形式幂级数的视角下，$x$ 只是系数的货架标签，所有运算只涉及有限次加法和乘法（提取 $x^n$ 系数时，更高次项一律写成 $O(x^{n+1})$ 扔掉）。需要分析收敛性的场合（渐近估计、鞍点法）超出了本章范围。

系数提取时数错。 乘积中 $x^n$ 的系数是所有”因子指数凑成 $n$“的取法之和，漏项、重复是最常见的错。两个补救办法：一是像例题 1 那样只保留需要的阶，把每个因子的级数在 $O(x^{n+1})$ 处截断再乘；二是用独立方法（小规模枚举）核对头几个系数，对上了再推广。

移位时下标对不齐。 由 ${\sum }_{n\ge 1}{a}_{n-1}{x}^n=xG(x)$ 这类平移，最容易错的是初值项的处理：先把 $G(x)-a_0$ 对齐递推的起始下标，再提因子。例题 3 中左边是 $G(x)-x$ 而不是 $G(x)$，就是因为 $F_0,F_1$ 两项都要先摘掉。

练习

练习 1. 写出数列 $a_n=n+1$（$n\ge 0$）的普通生成函数，并表示成有理函数形式。

答案：${\sum }_{n\ge 0}(n+1)x^n$。由 $\frac{1}{(1-x{)}^2}={\sum }_{n\ge 0}\left(\genfrac{}{}{0ex}{}{n+1}{1}\right)x^n={\sum }_{n\ge 0}(n+1)x^n$，得 $G(x)=\frac{1}{(1-x{)}^2}$。（提示：对几何级数求导再整理，也能得到同一结果。）

练习 2. 求 $\frac{1}{(1-x{)}^3}$ 中 $x^5$ 的系数。

答案：用级数库第四条，$\left(\genfrac{}{}{0ex}{}{5+3-1}{3-1}\right)=\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$。组合验证：不定方程 $y_1+y_2+y_3=5$ 的非负整数解数，隔板法给出 $\left(\genfrac{}{}{0ex}{}{7}{2}\right)=21$。

练习 3. 求不定方程 $x_1+x_2+x_3=n$ 满足 $x_1\ge 1$，$x_2\ge 2$，$x_3\ge 0$ 的整数解个数。

答案：三个约束对应因子 $\frac{x}{1-x}$、$\frac{x^2}{1-x}$、$\frac{1}{1-x}$，乘积为 $\frac{x^3}{(1-x{)}^3}$。$x^n$ 的系数等于 $\frac{1}{(1-x{)}^3}$ 中 $x^{n-3}$ 的系数，即 $\left(\genfrac{}{}{0ex}{}{(n-3)+2}{2}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$（$n\ge 3$；$n<3$ 时为 0）。可用代换 $y_1=x_1-1,y_2=x_2-2$ 化为标准隔板问题复核。

练习 4. 用生成函数解递推 $a_n=5a_{n-1}-6a_{n-2}(n\ge 2)$，初值 $a_0=2,a_1=5$。

答案：设 $G(x)=\sum a_n{x}^n$，代入求和得 $G(x)-2-5x=5x(G(x)-2)-6x^{2}G(x)$，整理：

$$G(x)=\frac{2-5x}{1-5x+6x^2}=\frac{2-5x}{(1-2x)(1-3x)}=\frac{1}{1-2x}+\frac{1}{1-3x},$$

（部分分式：解 $A(1-3x)+B(1-2x)=2-5x$，得 $A=B=1$。）展开得 $a_n=2^n+3^n$。核对初值：$a_0=2$，$a_1=2+3=5$，且 $2^n+3^n$ 显然满足递推。

学习路径

• 返回 离散数学总览
• 返回 数学基础专题首页
• PREV：递归与递推
• NEXT：代数结构