普通生成函数

序列 $a$ 的普通生成函数（ordinary generating function，OGF）定义为形式幂级数：

F (x) = \sum_{n} a_{n} x^{n}

$a$ 既可以是有穷序列，也可以是无穷序列。常见的例子（假设 $a$ 以 $0$ 为起点）：

序列 $a = ⟨ 1, 2, 3 ⟩$ 的普通生成函数是 $1 + 2 x + 3 x^{2}$ 。
序列 $a = ⟨ 1, 1, 1, \dots ⟩$ 的普通生成函数是 $\sum_{n \geq 0} x^{n}$ 。
序列 $a = ⟨ 1, 2, 4, 8, 16, \dots ⟩$ 的生成函数是 $\sum_{n \geq 0} 2^{n} x^{n}$ 。
序列 $a = ⟨ 1, 3, 5, 7, 9, \dots ⟩$ 的生成函数是 $\sum_{n \geq 0} (2 n + 1) x^{n}$ 。

换句话说，如果序列 $a$ 有通项公式，那么它的普通生成函数的系数就是通项公式。

基本运算

考虑两个序列 $a, b$ 的普通生成函数，分别为 $F (x), G (x)$ 。那么有

F (x) \pm G (x) = \sum_{n} (a_{n} \pm b_{n}) x^{n}

因此 $F (x) \pm G (x)$ 是序列 $⟨ a_{n} \pm b_{n} ⟩$ 的普通生成函数。

考虑乘法运算，也就是卷积：

F (x) G (x) = \sum_{n} x^{n} \sum_{i = 0}^{n} a_{i} b_{n - i}

因此 $F (x) G (x)$ 是序列 $⟨ \sum_{i = 0}^{n} a_{i} b_{n - i} ⟩$ 的普通生成函数。

封闭形式

在运用生成函数的过程中，我们不会一直使用形式幂级数的形式，而会适时地转化为封闭形式以更好地化简。

例如 $⟨ 1, 1, 1, \dots ⟩$ 的普通生成函数 $F (x) = \sum_{n \geq 0} x^{n}$ ，我们可以发现

F (x) x + 1 = F (x)

那么解这个方程得到

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

这就是 $\sum_{n \geq 0} x^{n}$ 的封闭形式。

考虑等比数列 $⟨ 1, p, p^{2}, p^{3}, p^{4}, \dots ⟩$ 的生成函数 $F (x) = \sum_{n \geq 0} p^{n} x^{n}$ ，有

\begin{aligned} F (x) p x + 1 & = F (x) \\ F (x) & = \frac{1}{1 - p x} \end{aligned}

等比数列的封闭形式与展开形式是常用的变换手段。

小练习

请求出下列数列的普通生成函数（形式幂级数形式和封闭形式）。难度是循序渐进的。

$a = ⟨ 0, 1, 1, 1, 1, \dots ⟩$ 。
$a = ⟨ 1, 0, 1, 0, 1, \dots ⟩$ 。
$a = ⟨ 1, 2, 3, 4, \dots ⟩$ 。
$a_{n} = (\binom{m}{n})$ （ $m$ 是常数， $n \geq 0$ ）。
$a_{n} = (\binom{m + n}{n})$ （ $m$ 是常数， $n \geq 0$ ）。

答案

第一个：

F (x) = \sum_{n \geq 1} x^{n} = \frac{x}{1 - x}

第二个：

\begin{aligned} F (x) & = \sum_{n \geq 0} x^{2 n} \\ = \sum_{n \geq 0} (x^{2})^{n} \\ = \frac{1}{1 - x^{2}} \end{aligned}

第三个（求导）：

\begin{aligned} F (x) & = \sum_{n \geq 0} (n + 1) x^{n} \\ = \sum_{n \geq 1} n x^{n - 1} \\ = \sum_{n \geq 0} (x^{n})^{'} \\ = {(\frac{1}{1 - x})}^{'} \\ = \frac{1}{(1 - x)^{2}} \end{aligned}

第四个（二项式定理）：

F (x) = \sum_{n \geq 0} (\binom{m}{n}) x^{n} = (1 + x)^{m}

第五个：

F (x) = \sum_{n \geq 0} (\binom{m + n}{n}) x^{n} = \frac{1}{(1 - x)^{m + 1}}

可以使用归纳法证明。

首先当 $m = 0$ 时，有 $F (x) = \frac{1}{1 - x}$ 。

而当 $m > 0$ 时，有

\begin{aligned} \frac{1}{(1 - x)^{m + 1}} & = \frac{1}{(1 - x)^{m}} \frac{1}{1 - x} \\ = (\sum_{n \geq 0} (\binom{m + n - 1}{n}) x^{n}) (\sum_{n \geq 0} x^{n}) \\ = \sum_{n \geq 0} x^{n} \sum_{i = 0}^{n} (\binom{m + i - 1}{i}) \\ = \sum_{n \geq 0} (\binom{m + n}{n}) x^{n} \end{aligned}

斐波那契数列的生成函数

接下来我们来推导斐波那契数列的生成函数。

斐波那契数列定义为 $a_{0} = 0, a_{1} = 1, a_{n} = a_{n - 1} + a_{n - 2} (n > 1)$ 。设它的普通生成函数是 $F (x)$ ，那么根据它的递推式，我们可以类似地列出关于 $F (x)$ 的方程：

F (x) = x F (x) + x^{2} F (x) - a_{0} x + a_{1} x + a_{0}

那么解得

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

那么接下来的问题是，如何求出它的展开形式？

展开方式一

不妨将 $x + x^{2}$ 当作一个整体，那么可以得到

\begin{aligned} F (x) & = \frac{x}{1 - (x + x^{2})} \\ = x \sum_{k = 0}^{\infty} (x + x^{2})^{k} \\ = x \sum_{k = 0}^{\infty} \sum_{i = 0}^{k} (\binom{k}{i}) x^{k - i} (x^{2})^{i} \\ = \sum_{k = 0}^{\infty} \sum_{i = 0}^{k} (\binom{k}{i}) x^{k + i + 1} \\ = \sum_{n = 1}^{\infty} \sum_{i = 0}^{⌊ (n - 1) / 2 ⌋} (\binom{n - i - 1}{i}) x^{n} . \end{aligned}

最后一步中，令 $n = k + i + 1$ 并更换求和顺序。由此，可以得到通项公式：

a_{n} = \sum_{i = 0}^{⌊ (n - 1) / 2 ⌋} (\binom{n - i - 1}{i}) .

这并不是我们熟知的有关黄金分割比的形式。

展开方式二

考虑求解一个待定系数的方程：

\frac{A}{1 - a x} + \frac{B}{1 - b x} = \frac{x}{1 - x - x^{2}}

通分得到

\frac{A - A b x + B - a B x}{(1 - a x) (1 - b x)} = \frac{x}{1 - x - x^{2}}

待定项系数相等，我们得到

{\begin{cases} A + B = 0 \\ - A b - a B = 1 \\ a + b = 1 \\ a b = - 1 \end{cases}

解得

{\begin{cases} A = \frac{1}{\sqrt{5}} \\ B = - \frac{1}{\sqrt{5}} \\ a = \frac{1 + \sqrt{5}}{2} \\ b = \frac{1 - \sqrt{5}}{2} \end{cases}

那么我们根据等比数列的展开式，就可以得到斐波那契数列的通项公式：

\frac{x}{1 - x - x^{2}} = \sum_{n \geq 0} x^{n} \frac{1}{\sqrt{5}} ({(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{n})

这也被称为斐波那契数列的另一个封闭形式（ $\frac{x}{1 - x - x^{2}}$ 是一个封闭形式）。

对于任意多项式 $P (x), Q (x)$ ，生成函数 $\frac{P (x)}{Q (x)}$ 的展开式都可以使用上述方法求出。在实际运用的过程中，我们往往先求出 $Q (x)$ 的根，把分母表示为 $\prod (1 - p_{i} x)^{d_{i}}$ 的形式，然后再求分子。

当对分母进行因式分解但有重根时，每有一个重根就要多一个分式，如考虑生成函数

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

的系数的通项公式，那么有

G (x) = \frac{c_{0}}{1 - x} + \frac{c_{1}}{1 - 2 x} + \frac{c_{2}}{(1 - 2 x)^{2}}

解得

{\begin{cases} c_{0} & = 1 \\ c_{1} & = - 2 \\ c_{2} & = 2 \end{cases}

那么

[x^{n}] G (x) = 1 - 2^{n + 1} + (n + 1) \cdot 2^{n + 1}

牛顿二项式定理

我们重新定义组合数的运算：

(\binom{r}{k}) = \frac{r^{\underset{―}{k}}}{k!} (r \in C, k \in N)

注意 $r$ 的范围是复数域。在这种情况下。对于 $α \in C$ ，有

(1 + x)^{α} = \sum_{n \geq 0} (\binom{α}{n}) x^{n}

二项式定理其实是牛顿二项式定理的一个特殊情况。

卡特兰数的生成函数

参考 Catalan 数形式的代数推演。

应用

接下来给出一些例题，来介绍生成函数在 OI 中的具体应用。

食物

在许多不同种类的食物中选出 $n$ 个，每种食物的限制如下：

承德汉堡：偶数个
可乐：0 个或 1 个
鸡腿：0 个，1 个或 2 个
蜜桃多：奇数个
鸡块：4 的倍数个
包子：0 个，1 个，2 个或 3 个
土豆片炒肉：不超过一个。
面包：3 的倍数个

每种食物都是以「个」为单位，只要总数加起来是 $n$ 就算一种方案。对于给出的 $n$ 你需要计算出方案数，对 $10007$ 取模。

这是一道经典的生成函数题。对于一种食物，我们可以设 $a_{n}$ 表示这种食物选 $n$ 个的方案数，并求出它的生成函数。而两种食物一共选 $n$ 个的方案数的生成函数，就是它们生成函数的卷积。多种食物选 $n$ 个的方案数的生成函数也是它们生成函数的卷积。

在理解了方案数可以用卷积表示以后，我们就可以构造生成函数（标号对应题目中食物的标号）：

$\sum_{n \geq 0} x^{2 n} = \frac{1}{1 - x^{2}}$ 。
$1 + x$ 。
$1 + x + x^{2} = \frac{1 - x^{3}}{1 - x}$ 。
$\frac{x}{1 - x^{2}}$ 。
$\sum_{n \geq 0} x^{4 n} = \frac{1}{1 - x^{4}}$ 。
$1 + x + x^{2} + x^{3} = \frac{1 - x^{4}}{1 - x}$ 。
$1 + x$ 。
$\frac{1}{1 - x^{3}}$ 。

那么全部乘起来，得到答案的生成函数：

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

然后将它转化为展开形式（使用封闭形式练习中第五个练习）：

F (x) = \sum_{n \geq 1} (\binom{n + 2}{n - 1}) x^{n}

因此答案就是 $(\binom{n + 2}{n - 1}) = (\binom{n + 2}{3})$ 。

Sweet

「CEOI2004」Sweet

有 $n$ 堆糖果。不同的堆里糖果的种类不同（即同一个堆里的糖果种类是相同的，不同的堆里的糖果的种类是不同的）。第 $i$ 个堆里有 $m_{i}$ 个糖果。现在要吃掉至少 $a$ 个糖果，但不超过 $b$ 个。求有多少种方案。

两种方案不同当且仅当吃的个数不同，或者吃的糖果中，某一种糖果的个数在两个方案中不同。

$n \leq 10, 0 \leq a \leq b \leq 10^{7}, m_{i} \leq 10^{6}$ 。

在第 $i$ 堆吃 $j$ 个糖果的方案数（显然为 1）的生成函数为

F_{i} (x) = \sum_{j = 0}^{m_{i}} x^{j} = \frac{1 - x^{m_{i} + 1}}{1 - x}

因此总共吃 $i$ 个糖果的方案数的生成函数就是

G (x) = \prod_{i = 1}^{n} F_{i} (x) = (1 - x)^{- n} \prod_{i = 1}^{n} (1 - x^{m_{i} + 1})

现在我们要求的是 $\sum_{i = a}^{b} [x^{i}] G (x)$ 。

由于 $n \leq 10$ ，因此我们可以暴力展开 $\prod_{i = 1}^{n} (1 - x^{m_{i} + 1})$ （最多只有 $2^{n}$ 项）。

然后对 $(1 - x)^{- n}$ 使用牛顿二项式定理：

\begin{aligned} (1 - x)^{- n} & = \sum_{i \geq 0} (\binom{- n}{i}) (- x)^{i} \\ = \sum_{i \geq 0} (\binom{n - 1 + i}{i}) x^{i} \end{aligned}

我们枚举 $\prod_{i = 1}^{n} (1 - x^{m_{i} + 1})$ 中 $x^{k}$ 项的系数，假设为 $c_{k}$ 。那么它和 $(1 - x)^{- n}$ 相乘后，对答案的贡献就是

c_{k} \sum_{i = a - k}^{b - k} (\binom{n - 1 + i}{i}) = c_{k} ((\binom{n + b - k}{b - k}) - (\binom{n + a - k - 1}{a - k - 1}))

这样就可以 $O (b)$ 地求出答案了。

时间复杂度 $O (2^{n} + b)$ 。

本页面最近更新：2025/9/14 00:37:42，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：sshwy, StudyingFather, countercurrent-time, Enter-tainer, H-J-Granger, NachtgeistW, CCXXXI, AngelKitty, c-forrest, cjsoft, diauweb, Early0v0, ezoixx130, GekkaSaori, Ir1d, Konano, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, Suyun514, weiyong1024, GavinZhengOI, Gesrua, Great-designer, HeRaNO, hly1204, kxccc, lychees, Molmin, Peanut-Tang, purple-vine, Revltalize, schtonn, shuzhouliu, skylee03, SukkaW, xglight
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用