生成函数

生成函数是连接数列和函数的桥梁，是解决组合计数问题强有力的工具。

普通生成函数

以例子出发，数列 $\{a_n\},n\geq0$ 满足

$$a_{n+1}=2a_n+1,a_0=0 $$

令 $A(x)=\sum_{n\ge0}a_nx^n$ 是数列 $\{a_n\}$ 的 OGF，对上面的等式两边同时取 OGF。

$$\begin{aligned} \sum_{n\ge0}a_{n+1}x^n&=\sum_{n\ge0}(2a_{n} + 1)x^n\\ \frac{A(x)}{x}&=2A(x)+\sum_{n\ge0}x^n\\ \frac{A(x)}{x}&=2A(x)+\frac{1}{1-x}\\ A(x)&=\frac{x}{(1-x)(1-2x)}\end{aligned}$$

此时一个数列就被封装到一个小巧的函数里了，若得到一些关于数列的信息，可以从这个封闭形式得到。比如想知道数列的第 $n$ 项（及其通项公式），相当于得到多项式（幂级数）的第 $x^n$ 项的系数，记为 $[x^n]A(x)$ 。对于数列求解通项公式，一般可以求得它的生成函数封闭形式，再用各种方法得到，如分式分解或是一些更常规的代数运算。

在 OI 中可以把计数问题的一些不确定的量（的一些值、贡献……）作为数列，并用生成函数解决。

各种运算太繁琐懒得写了，反正都很好理解。

例题：[CEOI2004] Sweets

指数生成函数

与 OGF 大致相同，不过对于一个数列 $\{a_n\}$ ，令 EGF 为 $\hat A(x)=\sum_{n\ge0}\frac{a_n}{n!}x^n$ 。

可以发现， $\hat A(x)$ 同时也是数列 $\{\frac{a_n}{n!}\}$ 的 OGF。

例题：Lust