开始学生成函数了。
普通型生成函数
生成函数是形式幂级数，不必顾虑收敛性等问题。对于一个数列 ${f_n}$，定义其普通型生成函数（Ordinary Generating Function，简称 OGF ）为 $F(x)=\sum\limits_{n\ge 0}{f_n x^n}$。$f_n$ 是 $x^n$ 在 $F(x)$ 中的系数（Coefficient），也写作 $f_n = [x^n]F(x)$。
一些例子
$$\begin{aligned}
\sum\limits_{n\ge 0}[n = m]x^n &= x^m\\
\sum\limits_{n\ge 0}x^n &= \dfrac{1}{1 - x}
\end{aligned}$$
由上面的那个式子可以得到以下四条：
$$\begin{aligned}
\sum\limits_{n\ge m}x^n &= \dfrac{x^m}{1 - x}\\
\sum\limits_{n\ge 0}x^{nk} &= \dfrac{1}{1 - x^k}\\
\sum\limits_{n\ge 0}c^n x^n &= \dfrac{1}{1 - cx}\\
\sum\limits_{n\ge 0}\binom{n + k - 1}{n}x^n &= \dfrac{1}{(1 - x)^k}
\end{aligned}$$
利用泰勒展开可以得到以下三条：
$$\begin{aligned}
\sum\limits_{n\ge 0}\dfrac{x^n}{n!}&=e^x\\
\sum\limits_{n > 0}\dfrac{x^n}{n} &= \ln \dfrac{1}{1 - x}\\
\sum\limits_{n > 0}\dfrac{(-1)^{n - 1}x^n}{n} &= \ln (1 + x)
\end{aligned}$$
运算
设 $F(x),G(x)$ 为数列 ${f_n}, {g_n}$ 的 OGF。
$$\begin{aligned}
cF(x) &= \sum\limits_{n\ge 0}cf_nx^n\\
x^mF(x) &= \sum\limits_{n\ge m}f_{n - m}x^n\\
F(cx) &= \sum\limits_{n\ge 0}c^nf_{n}x^n\\
\frac{\mathrm{d}}{\mathrm{d}x}F(x) &= \sum\limits_{n\ge 0}(n + 1)f_{n + 1}x^n\\
\int_{0}^{x} F(x)\mathrm{d}x &= \sum\limits_{n > 0}\frac{f_{n - 1}}{n} x^n\\
F(x)G(x) &= \sum\limits_{n\ge 0}(\sum\limits_{i=0}^{n}f_i g_{n - i})x^n\\
F(G(x)) &= \sum\limits_{n\ge 0}f_n(G(x))^n
\end{aligned}$$
简单例题
Example 1
求数列 $a_n = \begin{cases}
1 &,n = 0\\
ta_{n - 1} + w^{n - 1} &,n > 0
\end{cases}$ 的通项公式。其中 $t, w > 0$。
设 ${a_n}$ 的普通型生成函数为 $A$ ，则有 $A = tAx + \sum\limits_{n = 0}w^{n}x^{n} = tAx + \dfrac{1}{1 - wx}$。
则解出 $A = \dfrac{1}{(1 - tx)(1 - wx)}$。
所以 $a_n = \displaystyle\sum\limits_{i=0}^{n} t^i w^{n - i} = \dfrac{t^{n + 1} - w^{n + 1}}{t - w}$。
Example 2
证明 $4^n = \sum\limits_{i=0}^{n}\binom{2i}{i}\binom{2n-2i}{2i}$。
设 $F = \sum\limits_{i\ge 0}\binom{2i}{i}x^i$，则需证 $F^2 = (1-4x)^{-1}$。
$(1 - 4x)^{-\frac{1}{2}} = \sum\limits_{n\ge 0}(-4)^n\dbinom{-\frac{1}{2}}{n}x^n = F$，证毕。
$$\begin{aligned}
\dbinom{-\frac{1}{2}}{n} &= \dfrac{(-\frac{1}{2})^{\underline{n}}}{n!}\\
&= \dfrac{\prod\limits_{i=1}^{n}(-\frac{2i - 1}{2})}{n!}\\
&= \dfrac{(-1)^n\prod\limits_{i=1}^{n}(2i - 1)}{2^n n!}\\
&= \dfrac{(-1)^n(2n)!}{4^n (n!)^2}\\
&= \dfrac{(-1)^n}{4^n}\binom{2n}{n}
\end{aligned}$$
Example 3
Catalan 数列：$f_n = [n = 0] + \sum\limits_{i = 0}^{n - 1}f_i f_{n - i - 1}$，求其通项公式。
易得其生成函数 $F(x)$ 有 $F(x) = 1 + x(F(x))^2$。
将 $F(x)$ 看作元而 $x$ 看作参，则 $F(x) = \dfrac{1\pm \sqrt{1 - 4x}}{2x}$。
由于 $f_0 = 1$，即 $\lim_{x\to 0}F(x) = 1$，故取 $F(x) = \dfrac{1 - \sqrt{1 - 4x}}{2x}$。
类似 Example 2 来化简它：
$\sqrt{1 - 4x} = \sum\limits_{n\ge 0}(-4)^n\dbinom{\frac{1}{2}}{n}x^n = -2\sum\limits_{n\ge 0}\dfrac{(2n - 2)!}{n!(n - 1)!}x^n$
故 $F(x) = \sum\limits_{n\ge 0}\dfrac{(2n)!}{n!(n + 1)!}x^n$，即 $f_n = \dfrac{(2n)!}{n!(n + 1)!}$。
指数型生成函数
指数型生成函数与用于处理组合问题的普通型生成函数相对，用于处理排列问题。对于一个数列 ${f_n}$，定义其指数型生成函数（Exponential Generating Function，简称 EGF ）为 $F(x)=\sum\limits_{n\ge 0}{f_n \dfrac{x^n}{n!}}$。
运算
设 $F(x),G(x)$ 为数列 ${f_n}, {g_n}$ 的 EGF。
大部分与 OGF 相同。
$$\begin{aligned}
F(x)G(x) &= \sum\limits_{n\ge 0}(\sum\limits_{i=0}^n \binom{n}{i}f_i g_{n - i})\dfrac{x^n}{n!}\\
\frac{\mathrm{d}}{\mathrm{d}x}F(x) &= \sum\limits_{n\ge 0}f_{n + 1}\dfrac{x^n}{n!}\\
\int_{0}^{x} F(x)\mathrm{d}x &= \sum\limits_{n > 0}f_{n - 1}\dfrac{x^n}{n!}\\
xF(x) &= \sum\limits_{n > 0} \dfrac{f_{n - 1}}{n}\cdot\dfrac{x^n}{n!}\\
\frac{1}{x}(F(x) - f_0) &= \sum\limits_{n\ge 0} f_{n + 1}\dfrac{x^n}{n!}
\end{aligned}$$
一些例子
$$\begin{aligned}
\sum\limits_{n\ge 0}\dfrac{x^n}{n!} &= e^x\\
\sum\limits_{n\ge 0}\dfrac{c^n x^n}{n!} &= e^{cx}\\
\sum\limits_{n\ge 0}\dfrac{n^\underline{k} x^n}{n!} &= x^k e^x\\
\sum\limits_{n > 0}(n - 1)!\dfrac{x^n}{n!} &= \ln\dfrac{1}{1 - x}
\end{aligned}$$
简单应用
Example 1 ——贝尔数
贝尔数 $w_n$ 为将 $n$ 个不同元素划分为任意多个无序非空子集的方案数。
考虑递推，枚举1所在的子集大小 $i$，则应从剩下 $n - 1$ 个中选择 $i - 1$ 个与1放在同一集合，而其他随便放。即 $w_n = [n = 0] + \sum\limits_{i = 1}^{n}\binom{n - 1}{i - 1}w_{n - i}$。
设其 EGF 为 $W(x)$，则：
$$\begin{aligned}
W(x) &= 1 + \displaystyle\int W(x) e^x \mathrm{d}x\\
\dfrac{\mathrm{d}W(x)}{\mathrm{d}x} &= W(x)e^x\\
\dfrac{\mathrm{d}W(x)}{W(x)} &= e^x\mathrm{d}x\\
\ln W(x) &z= e^x + C
\end{aligned}$$
代入 $W(0) = w_0 = 1$，可得 $C = -1$。
故 $W(x) = \exp(e^x - 1)$。这个式子的组合解释？
考虑到 $F = e^x - 1$ 就是「非空子集」的 EGF（对于任意 $n > 0$ 均有一种方法把 $n$ 个元素放进一个集合里），那么套一层exp即 $\exp F = \displaystyle\sum\limits_{k\ge 0}\dfrac{F^k}{k!}$。
$k$ 可以看作非空子集的个数，且非空子集无序，故除以 $k!$。
类似地，可以得到 $n$ 个不同元素划分为任意多个无序非空集合，大小为 $k$ 的集合价值为 $a_k$，一种方案的价值为所有划分成的非空集合的价值的积，求所有方案的价值和，答案的 EGF 即为 $\exp(A(x))$。
Example 2 ——简单无向连通图
求 $f_n$ 表示 $n$ 个点的简单无向连通图的个数（点带标号）。
先设 $g_n$ 表示 $n$ 个点的简单无向图的个数，即 $g_n = 2^{\binom{n}{2}}$。
那么 $n$ 个点的简单无向连通图，可以用 $g_n$ 减去不连通图的个数。不连通，则枚举1号点所在连通块大小 $k$。即：
$$f_n = g_n - \sum\limits_{i = 1}^{n - 1}\binom{n - 1}{i - 1}f_i g_{n - i}$$
移项，就得到 Example 1 中我们见过的式子：
$$g_n = \sum\limits_{i = 1}^{n}\binom{n - 1}{i - 1}f_i g_{n - i}$$
设 $F(x), G(x)$ 分别为 ${f_n},{g_n}$ 的 EGF，则 $G(x) = \exp F(x)$，即 $F(x) = \ln G(x)$。
于是我们得到ln的用处：如果我们知道了一个生成函数exp之后是什么，就可以把它ln回来。