====== 生成函数 ======

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

常见的生成函数形式：

  * 普通型生成函数（Ordinary Generating Function, OGF）：$F(x) = \sum_{i=0}^{\infty} a_i x^i$
  * 指数型生成函数（Exponential Generating Function, EGF）：$F(x) = \sum_{i=0}^{\infty} \dfrac {a_i}{i!} x^i$



OGF 的卷积表示组合，而 EGF 的卷积表示排列——之前没怎么理解这个说法，现在就比较明白了。考虑卷积结果的某一项 $x^n$：

  * 对 OGF 卷积 $F(x) = \prod_{i=1}^m F_i(x)$，我们只关注每种 $F_i(x)$ 性质的东西占了 $n$ 个物品中的多少，而不关注具体是哪几个物品，因此说是组合；
  * 对 EGF 卷积 $G(x) = \prod_{i=1}^m G_i(x)$，我们用组合数钦定了每种 $G_i(x)$ 性质的东西分别是 $n$ 个物品的哪几个，相当于 OGF 卷积中给选中的物品钦定编号，因此说是排列。



===== 普通型生成函数 =====

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

  * 完全背包生成函数

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

  * 不知道什么的生成函数

$$
\sum _{i=0} ^{\infty} a^i x^i = \dfrac 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 = \dfrac {1}{(1-x)^n}
$$

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

==== 普通型生成函数与可逆背包 ====

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

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

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




===== 指数型生成函数 =====

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

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

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

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

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

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



==== 指数型生成函数与集合划分 ====

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

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

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




**例子 1** [[https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%95%B0 | 贝尔数]] $B_n$ 表示将大小为 $n$ 的集合划分为非空集合的方案数。令 $G(x) = \sum_{i=1}^{\infty} \dfrac {x^i}{i!} = \mathrm{e}^x - 1$，则 $G(x)$ 的 $n$ 次项系数表示“选 $n$ 个数组成一个非空集合的方案数”。显然大小为 $n$ 的集合的一个划分中，每个子集都具有相同的性质（都来自 $G(x)$ 的某一项），因此有贝尔数生成函数 $F(x) = \mathrm{e}^{G(x)} = \mathrm{e}^{\mathrm{e}^x - 1}$。

另一种理解方式是，若 $n$ 由 $k$ 个子集构成，则 $G^k(x)$ 的 $n$ 次项系数对应了上述的方案数，而这 $k$ 个集合应当无序，故要乘 $\dfrac 1{k!}$，最终有

$$
\begin{aligned}
F(x) 
&= \sum_{k=0}^{\infty} \dfrac {G^k(x)}{k!}    \\
&= \mathrm{e}^{G(x)}
\end{aligned}
$$



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



**例子 3** 令 $F(x)$ 为 $n$ 个点的连通 DAG 个数，$G(x)$ 为**不要求连通**的 $n$ 个点的 DAG 个数，显然这也同样满足集合划分要求。证明不难，参考例子 1 即可。




===== 参考资料 =====

  - [[https://rqy.moe/Algorithms/generating-function/ | 生成函数简介 - _rqy's Blog]]