本文主要做一个归纳性的总结。

常见的生成函数形式：

• 普通型生成函数：$f(x) = \sum_{i=0}^{\infty} a_i x^i$
• 指数型生成函数：$f(x) = \sum_{i=0}^{\infty} \dfrac {a_i}{i!} x^i$

形式幂级数 $\sum_{i = 0} ^ {\infty} a^i x^i = \frac 1 {1 - ax}$ 并不太关注 $x$ 的取值是否使得式子收敛。给出一些常用生成函数的封闭形式：

• 完全背包生成函数

$$ \sum _{i=0} ^{\infty} x^{ai} = \frac 1{1-x^a} $$

• 不知道什么的生成函数

$$ \sum _{i=0} ^{\infty} a^i x^i = \frac 1{1-ax} $$

• 二项式形式的生成函数

$$ \sum _{i=0} ^{\infty} \binom ni x^i = (1+x)^n $$

• 广义二项式定理的生成函数

$$ \sum _{i=0} ^{\infty} \binom{n+i-1}{i}x^i = \frac {1}{(1-x)^n} $$

令：扩展组合数为 $\binom {-n}k = (-1)^k \binom {n+k-1}{k}$，这个展开就可以验证了。带入二项式定理中可以得到广义二项式定理（见上）。

一个非常棒的可逆背包题：2018 沈阳 ICPC 现场 M 题。

$$ \sum _{i=0} ^n x^{ai} = \frac {1-(x^a)^{n+1}}{1-x^a} $$

上面是个负方案的 01 背包，下面是个完全背包，没了。

一些常见的指数型生成函数化简技巧：

$$ \sum _{i=0} ^{\infty} \frac {x^{2i}}{(2i)!} = \frac {\mathrm{e}^x + \mathrm{e}^{-x}}2 $$

$$ \sum _{i=0} ^{\infty} \frac {x^{2i+1}}{(2i+1)!} = \frac {\mathrm{e}^x - \mathrm{e}^{-x}}2 $$

这个性质可以将生成函数化成封闭形式。反过来，也可以将封闭形式转化为级数形式：

$$ \mathrm{e}^{ax} = \sum _{i=0} ^{\infty} \frac {a^i x^i}{i!} $$

注意因为是求排列，所以一般最后要乘一个 $n!$。

考虑一些具有性质 $A$ 的东西的指数型生成函数 $F(x)$，现在把 $A$ 里面的东西当成基本元素，像选物品一样合在一起获得具有 $B$ 性质的东西（也就是 $B$ 是几个 $A$ 属性的东西拼成的），且 $B$ 的生成函数是 $G(x)$，则

$$ G(x) = \mathrm{e}^{F(x)} $$

例子 1 令 $F(x)$ 为 $n$ 个点的无向连通图个数，$G(x)$ 为 $n$ 个点的任意图数量（且显然 $G(x) = \sum _{i=0}^{\infty} 2^{i(i-1)/2}x^i$），因此 $F(x) = \ln G(x)$。

例子 2 令 $F(x)$ 为 $n$ 个点的连通 DAG 个数，$G(x)$ 为不要求连通的 $n$ 个点的 DAG 个数，显然这也同样满足集合划分要求。一个小证明：$G(x)$ 是 $F(x)$ 的一个划分，因此对 $G(x)$ 枚举它由几个 $F(x)$ 构成，即

$$ \begin{aligned} G(x) &= \sum _{i=0} ^{\infty} \frac {F^i(x)}{i!} \\ &= \mathrm{e}^{F(x)} \end{aligned} $$

利用该性质可以极大化简某些过程。

• 生成函数简介 - _rqy's Blog