生成函数是一种用级数的系数来表达数列的方法，是处理数列的最强有力的方法之一。在 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$，即 $z^{+\infty}=0$ 时才成立。
幸运的是，在生成函数中我们只关心 $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$ 和 $FG$ 看做三个数组，则对于 $FG$ 的每个元素，都有
$$ (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$ 项系数就是答案。
更高阶的生成函数运算
事实上这一类类多项式生成函数还可以求指数函数、对数函数、平方根甚至三角函数。其中，指数函数有组合意义，对数函数则是这一组合意义的反演。