生成函数入门笔记

· · 算法·理论

引言

参考了 oi-wiki，《离散数学基础及实验教程》。例题均来源于书上。

生成函数是组合数学中表示序列的一种强大工具，它把序列的项作为一个形式幂级数中变量 x 的幂的系数。

生成函数的定义

实数序列 a_0,a_1,\cdots,a_k,\cdots 的生成函数是无穷级数

G(x)=a_0+a_1x+a_2x^2+\dots+a_kx^k+\dots=\sum_{k=0}^{\infty}a_kx^k

例如序列 \{a_k\} 具有 a_k=3，a_k=k+1 和 a_k=2^k 的生成函数分别为

\sum_{k=0}^{\infty}3x^k,\sum_{k=0}^{\infty}(k+1)x^k,\sum_{k=0}^{\infty}2^kx^k

可以通过置 a_{n+1}=0,a_{n+2}=0,\cdots 把一个有限的序列 a_0,a_1,\cdots,a_n 扩充成一个无限的序列（后面补零），这样就可以定义一个实数的有限序列的生成函数。这个有限序列 \{a_n\} 的生成函数为

G(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n

例如，序列 1,1,1,1,1,1 的生成函数是 G(x)=1+x+x^2+x^3+x^4+x^5= \frac{x^6-1}{x-1}；设 m 是正整数，令 a_k=C_m^k,k=0,1,\cdots,m，那么序列 a_0,a_1,\cdots,a_m 的生成函数就是 G(x)=C_m^0+C_m^1x+\cdots+C_m^mx^m=(1+x)^m。

几个有用的生成函数以及证明方式

::cute-table{tuack} G(x) a_k 备注
(1+x)^n=\sum\limits_{k=0}^nC_n^kx^k C_n^k 二项式定理
(1+ax)^n=\sum\limits_{k=0}^nC_n^ka^kx^k C_n^ka^k 二项式定理，代换上式变量
\frac{1-x^{n+1}}{1-x}=\sum\limits_{k=0}^{n}x^k [k\le n]（当 k\le n 时为 1，否则为 0） 等比数列求和公式
\frac{1}{1-x}=\sum\limits_{k=0}^{\infty}x^k 1 直接展开验证 (1-x)\sum x^k=1，逐项抵消
\frac{1}{1-ax}=\sum\limits_{k=0}^{\infty}a^kx^k a^k 代换上式变量
\frac{1}{(1-x)^2}=\sum\limits_{k=0}^{\infty}(k+1)x^k k+1 由 \frac1{1-x}\cdot\frac1{1-x} 得到，两个全 1 序列的卷积得到
\frac{1}{(1-x)^n}=\sum\limits_{k=0}^{\infty}C_{n+k-1}^kx^k C_{n+k-1}^k \frac{1}{(1-x)^n}=(1+x+x^2+\cdots)^n，展开后 x^k 的系数等于方程 e_1+e_2+\cdots+e_n=k\ (e_i\ge 0)的非负整数解个数，等价于将 k 个无区别的球放入 n 个有标号盒子，每盒可空。用插板法，解数为 C_{k+n-1}^{n-1}=C_{n+k-1}^{k}
e^x=\sum\limits_{k=0}^{\infty}\frac{x^k}{k!}[^1] \frac{1}{k!} 泰勒展开：令 f(x)=e^x，则任意阶导数 f^{(k)}(0)=e^0=1。代入泰勒公式 f(x)=\sum \frac{f^{(k)}(0)}{k!}x^k 即得
\ln(1+x)=\sum\limits_{k=1}^{\infty}\frac{(-1)^{k+1}}{k}x^k=x-\frac{x^2}2+\frac{x^3}{3}-\frac{x^4}4+\cdots[^1] \frac{(-1)^{k+1}}{k} 逐项积分或微分方程可得

[^1]:上述 e^x 和 \ln(1+x) 作为形式幂级数（普通生成函数）依然成立（只需令 a_k=1/k! 等）。但在组合计数中，它们更常作为指数生成函数（EGF）出现，用于处理排列类问题。本文暂不展开 EGF，仅展示其形式幂级数的展开式。

生成函数求解计数问题

$C_n^r$ 的组合数是 $n$ 个**对象**中取 $r$ 个进行组合的方案数。考虑 $(1+x)^n$，这里有 $n$ 个**因子** $(1+x)$，代表 $n$ 个对象，其中每个因子有两项，$1=x^0$ 表示**没取到**该对象，$x$ 表示**取到**该对象，每个**因子**正好提供了这个**对象**取到或者没取到这两种**信息**。二项式展开时，$x^r$ 正是由于这些因子中有 $r$ 个取的是 $x$，$(n-r)$ 个取的是 $1$ 而产生的。即 $$x^r=x^{r_1+r_2+\dots+r_n}=x^{r_1}\cdot x^{r_2}\cdot\ \dots\ \cdot x^{r_n}$$ 其中 $$ r_k= \begin{cases} 0,&没取到第\ k\ 个对象\\ 1,&取到第\ k\ 个对象 \end{cases} $$ $$ \sum_{k=1}^{n}r_k=r $$ $x^r$ 前的系数 $C_n^r$ 应该是含 $x^r$ 的单项的系数之和，任意取到 $r$ 个对象都会构成一个 $x^r$ 的单项，$C_n^r$ 也正是 $n$ 个对象中任选 $r$ 个的方案数。把生成函数 $G(x)=(1+x)^n$ 看成是用这种思想**构造**出来的。注意，这里的“对象”在不同问题中有不同含义：在组合问题中它可以指具体的个体（如人），在方程求解中它可以指一个变量。关键是每个因子代表一个独立的选择维度。 有 $n$ 个**对象**就对应 $n$ 个**因子**，每个因子包括题意中可能出现的情况，如取到或取不到，取到的个数以 $x$ 的指数形式表示。把这种思想加以扩充，扩充到**一种对象可以取多个**的情况。从 $n$ 类可以**重复**选取的对象（充分供应）中，任取 $r$ 个的组合数，也就是有重复的组合问题，如果用生成函数来解，可以想到应该有 $n$ 个因子，由于每类对象都可以被**无限制**地选取，因此每个因子都形如 $(1+x+x^2+\cdots)$，$x$ 的指数正是此对象**被选取的次数**。我们可以构造下面的生成函数 $$G(x)=(1+x+x^2+\dots)^n=(\frac{1}{1-x})^n$$ 只需求展开式中 $x^r$ 前的系数 $a_r$ 就够了。 我们可以对 $G(x)=(\frac{1}{1-x})^n$ 求 $r$ 次导数： $$G^{(r)}(x)=n(n+1)\cdots(n+r-1)\frac1{(1-x)^{n+r}}$$ 令 $$G(x)=a_0+a_1x+\dots+a_rx^r+\dots+a_nx^n+\cdots$$ $$G^{(r)}(x)=a_rr!+a_{r+1}\cdot(r+1)r\cdots2\cdot x+\dots+a_n\cdot n(n-1)\cdots(n-r+1)\cdot x^{n-r}+\cdots$$ 将 $x=0$ 分别代入上式得 $$a_rr!=G^{(r)}(0)=n(n+1)\cdots(n+r-1)$$ $$a_r=\frac{n(n+1)\cdots(n+r-1)}{r!}=\frac{(n+r-1)!}{r!(n-1)!}=C_{n+r-1}^r$$ 我们就这样通过生成函数的方法得到了有重复的组合公式（和插板法结果一致）。 ### 例题 1 求 $x_1+x_2+x_3=11$ 的非负整数解中满足 $2\le x_1 \le 5,3\le x_2\le 4,2\le x_3\le 6$ 的个数。 对于对象 $x_1$ 要满足 $2\le x_1\le 5$，则对应因子为 $(x^2+x^3+x^4+x^5)$，同理对象 $x_2$ 对应的因子为 $(x^3+x^4)$，对象 $x_3$ 对应的因子为 $(x^2+x^3+x^4+x^5+x^6)$。 构造生成函数：$G(x)=(x^2+x^3+x^4+x^5)(x^3+x^4)(x^2+x^3+x^4+x^5+x^6)$。 为了求 $x^{11}$ 的系数，我们先**提取公因式**，减少后续乘法的项数： $$\begin{aligned}G(x) &= x^2(1+x+x^2+x^3)\cdot x^3(1+x)\cdot x^2(1+x+x^2+x^3+x^4) \\&= x^{7}(1+x+x^2+x^3)(1+x)(1+x+x^2+x^3+x^4)\end{aligned}$$ 因此，求 $G(x)$ 中 $x^{11}$ 的系数，等价于求 $H(x)=(1+x+x^2+x^3)(1+x)(1+x+x^2+x^3+x^4)$ 中 $x^4$ 的系数。 接下来我们用**截断乘法**求 $H(x)$ 中 $x^4$ 的系数（高于 $x^4$ 的项暂不关心，直接略去）。 $$(1+x+x^2+x^3)(1+x)=1+2x+2x^2+2x^3+x^4$$ 再乘 $(1+x+x^2+x^3+x^4)$，取 $x^4$ 系数为 $1+2+2+2+1=8$。因此 $G(x)$ 中 $x^{11}$ 的系数为 $8$，即满足条件的非负整数解个数为 $8$。 ### 例题 2 某单位有 $8$ 个男同志，$5$ 个女同志，现组织一个由偶数个男同志和不少于两个女同志组成的工作组，每种人数的工作组各有多少种组织法？ 男同志取偶数个有 $0,2,4,6,8$ 共五种情况，但是男同志不能看成一类对象，因为 $8$ 个人是不同的人，选取的人定下后选谁还有不同的方案。所以男同志对应的因子为 $(C_8^0+C_8^2x^2+C_8^4x^4+C_8^6x^6+C_8^8x^8)$，女同志同理可得。因此生成函数 $$\begin{aligned}G(x)&=(C_8^0+C_8^2x^2+C_8^4x^4+C_8^6x^6+C_8^8x^8)(C_5^2x^2+C_5^3x^3+C_5^4x^4+C_5^5x^5)\\&=10x^2+10x^3+285x^4+281x^5+840x^6+728x^7+630x^8+350x^9+150x^{10}+38x^{11}+5x^{12}+x^{13}\end{aligned}$$ 组织每种人数小组的方案数一目了然。 ## 生成函数求解递推关系 除了直接解决**计数**问题，生成函数还可以用来求解关于一个**递推关系和初始条件的解**。 说白了，生成函数可以根据递推关系和初始条件求出**序列的通项**。 我们先来看一个简单的数列：$a_k=3a_{k-1},k=1,2,\cdots,a_0=2$。 设 $G(x)$ 是序列 $\{a_n\}$ 的生成函数。 即 $$G(x)=\sum_{k=0}^{\infty}a_kx^k$$ $$3xG(x)=\sum_{k=0}^{\infty}3a_kx^{k+1}=\sum_{k=1}^{\infty}3a_{k-1}x^k$$ $$\begin{aligned}G(x)-3xG(x)&=\sum_{k=0}^{\infty}a_kx^k-\sum_{k=1}^{\infty}3a_{k-1}x^k\\&=a_0+\sum_{k=1}^{\infty}a_kx^k-\sum_{k=1}^{\infty}3a_{k-1}x^k\\&=a_0\end{aligned}$$ $$G(x)=\frac{a_0}{1-3x}=\frac2{1-3x}=2\sum_{k=0}^{\infty}3^kx^k=\sum_{k=0}^{\infty}2\cdot3^kx^k$$ 所以 $a_k=2\cdot3^k$。 这个方法对于求数列通项非常管用。下面是一道例题。 ### 例题 3 设一个有效的编码是一个包含偶数个零的 $n$ 位 $10$ 进制数字串。令 $a_n$ 表示 $n$ 位有效编码字的个数，求 $a_n$ 通项。 我们先求 $a_n$ 的**递推式**。 我们考虑前 $n-1$ 位 $0$ 个数的奇偶性。若前 $n-1$ 位中已经有偶数个 $0$，则最后一位不能是 $0$，能取 $1\sim 9$ 共 $9$ 种选择，贡献 $9a_{n-1}$。 若前 $n-1$ 位中有奇数个 $0$，则最后一位必须是 $0$，只有 $1$ 种选择。前 $n-1$ 位共有奇数个 $0$ 的个数有 $10^{n-1}-a_{n-1}$ 种，贡献 $10^{n-1}-a_{n-1}$。 因此 $a_n=9a_{n-1}+(10^{n-1}-a_{n-1})=8a_{n-1}+10^{n-1}$，初始值 $a_0=1$（空串含偶数个零）。 然后我们使用生成函数**求解通项**。 序列 $\{a_n\}$ 的生成函数 $$G(x)=\sum_{k=0}^{\infty}a_kx^k$$ $$8xG(x)=\sum_{k=0}^{\infty}8a_kx^{k+1}=\sum_{k=1}^{\infty}8a_{k-1}x^k$$ $$\begin{aligned}(1-8x)G(x)&=G(x)-8xG(x)\\&=\sum_{k=0}^{\infty}a_kx^k-\sum_{k=1}^{\infty}8a_{k-1}x^k\\&=a_0x^0+\sum_{k=1}^{\infty}a_kx^k-\sum_{k=1}^{\infty}8a_{k-1}x^k\\&=1+\sum_{k=1}^{\infty}(a_k-8a_{k-1})x^k\\&=1+\sum_{k=1}^{\infty}10^{k-1}x^k\\&=1+x\sum_{k=1}^{\infty}10^{k-1}x^{k-1}\\&=1+x\sum_{k=0}^{\infty}10^kx^k\\ &=1+x\cdot\frac{1}{1-10x}\\&=\frac{1-10x}{1-10x}+\frac{x}{1-10x}\\&=\frac{1-9x}{1-10x}\end{aligned}$$ $$\begin{aligned}G(x)&=\frac{1-9x}{(1-10x)(1-8x)}\\&=\frac1{2(1-10x)}+\frac1{2(1-8x)}\\&=\frac12\sum_{k=0}^{\infty}10^kx^k+\frac12\sum_{k=0}^{\infty}8^kx^k\\&=\frac12\sum_{k=0}^{\infty}(10^k+8^k)x^k\end{aligned}$$ 所以 $a_n=\frac12(10^n+8^n)$。 ### 例题 4 现在我们用生成函数求斐波那契数列的通项。$a_n=a_{n-1}+a_{n-2},a_1=a_2=1$。 我们先补充 $a_0=0$。 设序列 $\{a_n\}$ 的生成函数为 $G(x)$。 $$G(x)=\sum_{k=0}^{\infty}a_kx^k$$ $$xG(x)=\sum_{k=0}^{\infty}a_kx^{k+1}$$ $$x^2G(x)=\sum_{k=0}^{\infty}a_kx^{k+2}$$ $$\begin{aligned}(1-x-x^2)G(x)&=\sum_{k=0}^{\infty}a_kx^k-\sum_{k=0}^{\infty}a_kx^{k+1}-\sum_{k=0}^{\infty}a_kx^{k+2}\\&=a_0+a_1x+\sum_{k=2}^{\infty}a_kx^k-a_0x-\sum_{k=1}^{\infty}a_kx^{k+1}-\sum_{k=0}^{\infty}a_kx^{k+2}\\&=x+\sum_{k=0}^{\infty}a_{k+2}x^{k+2}-\sum_{k=0}^{\infty}a_{k+1}x^{k+2}-\sum_{k=0}^{\infty}a_kx^{k+2}\\&=x+\sum_{k=0}^{\infty}(a_{k+2}-a_{k+1}-a_{k})x^{k+2}\\&=x\end{aligned}$$ 设 $\frac{x}{1-x-x^2}=\frac{A}{1-\alpha x}+\frac{B}{1-\beta x}$，待定系数解得 $A=-B=\frac{1}{\sqrt5}$，其中 $\alpha,\beta=\frac{1\pm\sqrt5}{2}$。 $$\begin{aligned}G(x)&=\frac x{1-x-x^2}\\&=\frac1{\sqrt5(1-\frac{1+\sqrt5}2x)}-\frac1{\sqrt5(1-\frac{1-\sqrt5}2x)}\\&=\frac1{\sqrt5}\sum_{k=0}^{\infty}\left(\frac{1+\sqrt5}2\right)^kx^k-\frac1{\sqrt5}\sum_{k=0}^{\infty}\left(\frac{1-\sqrt5}2\right)^kx^k\\&=\frac1{\sqrt5}\sum_{k=0}^{\infty}\left[\left(\frac{1+\sqrt5}2\right)^k-\left(\frac{1-\sqrt5}2\right)^k\right]x^k\end{aligned}$$ 所以 $a_n=\frac1{\sqrt5}\left[\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n\right]$。 ## 小结 回顾全文，生成函数的关键是“**构造级数，提取系数**”，主要用于解决以下两类问题： 1. **组合计数问题**：关键在于**构造因子**。每个独立的选择对象（或变量）对应一个因子，因子中 $x$ 的指数代表该对象贡献的数量。将所有因子相乘后，目标方案数就是展开式中对应 $x^k$ 项的系数。实际计算时，常通过提取公因式或截断乘法来简化系数求解。 2. **递推数列问题**：关键在于**建立方程**。设序列 $\{a_n\}$ 的生成函数为 $G(x)$，利用递推关系将 $G(x)$ 表示成封闭形式（通常为有理分式）。通过部分分式分解，将其拆解为若干已知展开式的组合，最后直接读取 $x^n$ 的系数，即可得到通项公式 $a_n$。 作为一篇入门教程，本文仅讨论了**普通生成函数（OGF）**，它适用于组合（顺序无关）场景。当问题涉及排列（顺序相关）或带阶乘标记的复杂结构时，**指数生成函数（EGF）** 将是更趁手的工具，值得进一步深入学习。