普通生成函数

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

F (x) = n \sum 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) = n \sum (a_{n} \pm b_{n}) x^{n}

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

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

F (x) G (x) = n \sum x^{n} i = 0 \sum 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}$ ，有

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

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

小练习

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

$a = ⟨ 0, 1, 1, 1, 1, \dots ⟩$ 。

$a = ⟨ 1, 0, 1, 0, 1, \dots ⟩$ 。

$a = ⟨ 1, 2, 3, 4, \dots ⟩$ 。

$a_{n} = (n m)$ （ $m$ 是常数， $n \geq 0$ ）。

$a_{n} = (n m + n)$ （ $m$ 是常数， $n \geq 0$ ）。

答案

第一个：
$F (x) = n \geq 1 \sum x^{n} = \frac{x}{1 - x}$
第二个：
$F (x) = n \geq 0 \sum x^{2 n} = n \geq 0 \sum (x^{2})^{n} = \frac{1}{1 - x ^{2}}$
第三个（求导）：
$F (x) = n \geq 0 \sum (n + 1) x^{n} = n \geq 1 \sum n x^{n - 1} = n \geq 0 \sum (x^{n})^{'} = (\frac{1}{1 - x})^{'} = \frac{1}{( 1 - x ) ^{2}}$
第四个（二项式定理）：
$F (x) = n \geq 0 \sum (n m) x^{n} = (1 + x)^{m}$
第五个：
$F (x) = n \geq 0 \sum (n m + n) x^{n} = \frac{1}{( 1 - x ) ^{m + 1}}$
可以使用归纳法证明。

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

而当 $m > 0$ 时，有
$\frac{1}{( 1 - x ) ^{m + 1}} = \frac{1}{( 1 - x ) ^{m}} \frac{1}{1 - x} = (n \geq 0 \sum (n m + n - 1) x^{n}) (n \geq 0 \sum x^{n}) = n \geq 0 \sum x^{n} i = 0 \sum n (i m + i - 1) = n \geq 0 \sum (n m + n) x^{n}$

斐波那契数列的生成函数

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

斐波那契数列定义为 $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}$ 当作一个整体，那么可以得到

F (x) = \frac{x}{1 - ( x + x ^{2} )} = x k = 0 \sum \infty (x + x^{2})^{k} = x k = 0 \sum \infty i = 0 \sum k (i k) x^{k - i} (x^{2})^{i} = k = 0 \sum \infty i = 0 \sum k (i k) x^{k + i + 1} = n = 1 \sum \infty i = 0 \sum ⌊(n - 1) /2 ⌋ (i n - i - 1) x^{n} .

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

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

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

展开方式二

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

\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}}

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

⎩ ⎨ ⎧ A + B = 0 - A b - a B = 1 a + b = 1 ab = - 1

解得

⎩ ⎨ ⎧ A = \frac{1}{5} B = - \frac{1}{5} a = \frac{1 + 5}{2} b = \frac{1 - 5}{2}

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

\frac{x}{1 - x - x ^{2}} = n \geq 0 \sum x^{n} \frac{1}{5} ((\frac{1 + 5}{2})^{n} - (\frac{1 - 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}}

解得

⎩ ⎨ ⎧ c_{0} c_{1} c_{2} = 1 = - 2 = 2

那么

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

牛顿二项式定理

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

(k r) = \frac{r ^{\underline{k}}}{k !} (r \in C, k \in N)

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

(1 + x)^{α} = n \geq 0 \sum (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$ 个的方案数的生成函数也是它们生成函数的卷积。

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

$n \geq 0 \sum 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}}$ 。
$n \geq 0 \sum 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) = n \geq 1 \sum (n - 1 n + 2) x^{n}

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

Sweet

「CEOI2004」Sweet

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

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

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

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

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

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

G (x) = i = 1 \prod n F_{i} (x) = (1 - x)^{- n} i = 1 \prod 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}$ 使用牛顿二项式定理：

(1 - x)^{- n} = i \geq 0 \sum (i - n) (- x)^{i} = i \geq 0 \sum (i n - 1 + i) x^{i}

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

c_{k} i = a - k \sum b - k (i n - 1 + i) = c_{k} ((b - k n + b - k) - (a - k - 1 n + a - k - 1))

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

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

Sean's Blog

探索

普通生成函数

基本运算

封闭形式

斐波那契数列的生成函数

展开方式一

展开方式二

牛顿二项式定理

卡特兰数的生成函数

应用

食物

Sweet

目录

关系图谱

目录