简单介绍生成函数

生成函数是一种用级数的系数来表达数列的方法，是处理数列的最强有力的方法之一。在 OI 中生成函数常常与多项式结合起来处理计数问题。

几种基本的生成函数

对于一个无限长度的数列 $a_0, a_1, a_2, \ldots$，它的普通型生成函数 (Ordinary Generating Function, OGF) 是

$$F(z)=a_0+a_1z+a_2z+\ldots+a_iz^i+\ldots$$

它的指数型生成函数 (Exponential Generating Function, EGF) 是

$$F(z)=\dfrac{a_0}{0!}+\dfrac{a_1z}{1!}+\dfrac{a_2z^2}{2!}+\ldots+\dfrac{a_iz^i}{i!}+\ldots$$

还有另一种较为特殊的狄利克雷型生成函数，暂时不提。

普通型生成函数

普通型生成函数是我们最常用的生成函数。在这之后，如果不说明是何种生成函数，默认是在指普通型生成函数。

数列 $1,1,1,\ldots$ 的普通型生成函数是什么？

这个问题似乎很无趣。让我们把它写下来

$$F(z)=1+z+z^2+\ldots\\ zF(z)=z+z^2+z^3+\ldots$$

我们发现

$$F(z)-zF(z)=1\\ F(z)=\dfrac{1}{1-z}$$

事实上，$1+z+z^2+\ldots$ 是 $F(z)$ 的开放形式，而 $\dfrac{1}{1-z}$ 是 $F(z)$ 的封闭形式。用相同的方法，我们能得到所有类似数列的普通型生成函数的封闭形式：

$$F(z)=1+az+a^2z^2+a^3z^3\ldots=\dfrac{1}{1-az}\\ G(z)=1+z^{a}+z^{2a}+z^{3a}+\ldots=\dfrac{1}{1-z^a}$$

注意

如果你把 $z=10$ 代入 $1+z+z^2+\ldots=\dfrac{1}{1-z}$，你会发现这个式子根本不成立。事实上，这个式子只有在 $|z|<1$ 时才成立。

幸运的是，在生成函数中我们只关心 $F(z)$ 的系数，不关心 $z$ 的值和 $F(z)$ 的值。可以认为这些封闭形式在我们研究的范围内总是成立的。

数列 $\binom{n}{0},\binom{n}{1},\binom{n}{2},\ldots,\binom{n}{i},\ldots$ 的普通型生成函数是什么？

这个问题和上面那个大同小异。直接写出来

$$F(z)=\binom{n}{0}+\binom{n}{1}z+\binom{n}{2}z^2+\ldots$$

这符合二项式定理的形式。用二项式定理得到原式的封闭形式：

$$F(z)=(1+z)^n$$

看来很多数列都有封闭形式！斐波那契数列是否也有封闭形式？

$$F(z)=1+z+2z^2+3z^3+5z^4+8z^7+\ldots$$

因为 $f_n=f_{n-1}+f_{n-2}$，于是对于原函数的每一项 $f_iz^i$，我们都可以用 $f_iz^i=z\cdot f_{i-1}z^{i-1}+z^2\cdot f_{i-2}z^{i-2}$ 替换

$$F(z)=1+zF(z)+z^2F(z)$$

解得

$$F(z)=\dfrac{1}{1-z-z^2}$$

普通型生成函数卷积

生成函数如果不能进行运算，那它将是无用的。我们先介绍生成函数的卷积运算。你也可以认为卷积就是乘法。

普通型生成函数的卷积与多项式类似。设普通型生成函数 $F(z)=\sum\limits_{i=0} f_iz^i$ 和 $G(z)=\sum\limits_{i=0} g_iz^i$，则有 $(F*G)(z)=\sum\limits_{i=0}\sum\limits_{j=0}^if_jg_{i-j}z^i$。这样定义是很自然的，因为乘法分配律。

我们发现这像是一个动态规划的转移。如果把 $F$，$G$ 和 $F*G$ 看做三个数组，则对于 $F*G$ 的每个元素，都有

$$(F*G)[i]=F[0]\times G[i]+F[1]\times G[i-1]+F[2]\times G[i-2]+F[3]\times G[i-3]+\ldots+F[i]\times G[0]$$

这个 DP 的转移原本是 $O(n^2)$ 的。但如果我们把它看成生成函数的卷积，就可以在 $O(n\log n)$ 的时间复杂度内计算。

当然，生成函数不止能优化时间，它还是一种更简便的计算工具。参考下面的例题：

野餐

你们家将要外出野餐，由你负责准备食物。你打算携带一些水、牛奶、饼干、三明治和火腿。考虑到食物搭配合理，你准备的食物要满足如下条件：

• 水携带任意瓶
• 牛奶携带 $0$ 瓶或 $2$ 瓶
• 饼干携带 $3$ 盒或 $4$ 盒
• 三明治携带偶数份
• 火腿携带奇数份

求如果携带 $1000$ 件食物，你有多少种携带方案。两个方案不同当且仅当在这两种方案中，某种食物的数量不同。

携带水的方案数形成的数列是 $1, 1, 1, \ldots$ (携带任意瓶水的方案数都是 $1$)。由前面介绍的知识可知携带水的方案数的生成函数是 $\dfrac{1}{1-x}$。

携带牛奶的方案数形成的数列是 $1, 0, 1, 0, 0, 0 \ldots$ (只有携带 $0$ 瓶或 $2$ 瓶的方案数是 $1$)。它的生成函数是 $1+x^2$。

携带饼干的方案数形成的数列是 $0, 0, 0, 1, 1, 0, 0, \ldots$。它的生成函数是 $x^3+x^4$。

携带三明治的方案数形成的数列是 $1, 0, 1, 0, 1, 0, \ldots$。它的生成函数是 $1+x^2+x^4+x^6+\ldots=\dfrac{1}{1-x^2}$。

携带火腿的方案数形成的数列是 $0, 1, 0, 1, 0, 1, \ldots$。它的生成函数是 $\dfrac{x}{1-x^2}$。

由于转移的形式与生成函数的卷积的形式完全吻合，这些生成函数的卷积的 $x^{1000}$ 次项的系数就是答案。于是携带食物的方案数形成的数列的生成函数是

$$\dfrac{1}{1-x}(1+x^2)(x^3+x^4)\dfrac{1}{1-x^2}\dfrac{x}{1-x^2}=\dfrac{x^4+x^5+x^6+x^7}{(1-x)(1-x^2)^2}$$

由于包含除法，我们现在还不会求 $\dfrac{x^4+x^5+x^6+x^7}{(1-x)(1-x^2)^2}$ 的系数。但我们已经得到了复杂情况的简洁表达方式。

指数型生成函数

为什么指数型生成函数被称为指数型生成函数，而不是阶乘型生成函数？因为指数函数的麦克劳林级数是

$$e^x = \sum\limits_{i=0}^{+\infty}\dfrac{x^i}{i!}$$

我们也常把 $e^x$ 写作 $\exp x$。可以看出 $\exp x$ 正好与指数型生成函数的形式吻合。

由于 $\binom{n}{m}=\dfrac{n!}{m!(n-m)!}$，指数型生成函数的卷积恰好满足 $(F*G)(z)=\sum\limits_{i=0}\sum\limits_{j=0}^i\binom{i}{j}f_jg_{i-j}z^i$，正好比 OGF 多了一个二项式系数。下面的例题可以帮助理解这里的二项式系数的作用。

基因

科学家最近在火星上发现了一种原始生物。这种原始生物也是以 DNA 作为遗传物质的。

我们可以用一个仅含 $\texttt{A,T,G,C}$ 的字符串来描述这个生物的某个基因片段。经过研究，科学家发现这个字符串满足如下限制：

• $\texttt{A}$ 的出现次数为偶数
• $\texttt{T}$ 的出现次数为奇数

求有多少个满足如上限制且长度为 $n$ 的字符串。

由于字符间的不同顺序也要计入方案，在转移时我们要乘上对应的二项式系数。指数型生成函数正好可以担负这一任务。

$\texttt{A}$ 的方案数的指数型生成函数是 $1+\dfrac{x^2}{2!}+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\ldots=\dfrac{e^x + e^{-x}}{2}$。

$\texttt{T}$ 的方案数的指数型生成函数是 $\dfrac{x}{1!}+\dfrac{x^3}{3!}+\dfrac{x^5}{5!}+\ldots=\dfrac{e^x-e^{-x}}{2}$。

$\texttt{G}$ 和 $\texttt{C}$ 的方案数的指数型生成函数都是 $e^x$。

于是字符串的方案数的指数型生成函数就是

$$\dfrac{e^x + e^{-x}}{2}\dfrac{e^x - e^{-x}}{2}e^xe^x=\dfrac{e^{4x}-1}{4}$$

用麦克劳林级数展开就可以得到各项系数了。这个生成函数的第 $n$ 项系数就是答案。

更高阶的生成函数运算

之前我们介绍了生成函数的乘法 (卷积)，但事实上这一类类多项式生成函数还可以求指数函数、对数函数、开平方根甚至求三角函数！其中，指数函数有组合意义，对数函数则是这一组合意义的反演。下面给出了几道参考的例题，在掌握了多项式的相关科技后可以去做，理解生成函数的强大。

付公主的背包
The Child and Binary Tree

评论