生成函数

很有用。

0.写在前面

无论是 OGF 还是 EGF，往往都具有很好的数学性质。而很多问题之所以可以用GF解决，因为我们可以将组合问题转化为研究GF的数学性质，再利用多项式科技解决。

所以说到底应该如何理解 GF？

1.普通生成函数 OGF

从 DP 的角度看，形式幂级数之间的相乘与不同状态间的转移等价，其中 $x^n$ 表示状态，系数 $a_n$ 表示该状态的答案。

1.1 封闭形式

记几个式子，$F(x)$ 为序列 $a$ 的生成函数所对应的封闭形式：

$$\begin{align} &a_n=\binom{m}{n}\Rightarrow F(x)=\sum_{n\ge0} \binom{m}{n} x^n=(1+x)^m\\ &a_n=\binom{m+n}{n} \Rightarrow F(x)=\sum_{n\ge0} \binom{m+n}{n}x^n=\frac{1}{(1-x)^{m+1}}\notag\\ \end{align}$$

还有一些经典式子：

$$\ln \frac{1}{1-x^k}=\sum_{i>0}\frac{1}{i}x^{ik}$$

1.2 卷积

$$\begin{align} F(x)&=\sum_{i\ge 0} a_nx^i\notag\\ G(x)&=\sum_{i\ge 0} b_nx^i\notag\\ F(x)*G(x)&=\sum_{n\ge 0}x^n\sum_{i\ge 0}a_i b_{n-i}\notag\\ \end{align}$$

直接卷积得到的新的生成函数，而这个生成函数系数的系数除了卷积得到的系数外，没有其他系数。从排列组合的角度理解，说明不同元素之间相对顺序的改变不会影响方案总数，故这样求出来是无标号的。

2.指数生成函数

或许还是可以从 DP 的角度理解，不同点是系数 $\frac{1}{i!}$，这可以用来代表 DP 转移中乘上的系数。

2.1 封闭形式

2.2 卷积

考虑两个EGF $\hat{F}(x)$ 和 $\hat{G}(x)$ 的卷积：

$$\begin{align} \hat{F}(x)&=\sum_{i\ge 0} a_n\frac{x^i}{i!} \notag\\ \hat{G}(x)&=\sum_{i\ge 0} b_n\frac{x^i}{i!} \notag\\ \hat{F}(x)*\hat{G}(x)&=\sum_{n\ge 0}x^n\sum_{i\ge 0}a_i b_{n-i} \frac{1}{i!(n-i)!}\notag\\ &=\sum_{n\ge 0}\frac{x^n}{n!}\sum_{i\ge 0}\binom{n}{i}a_i b_{n-i} \end{align}$$

我们得到一个新的指数生成函数，这个指数生成函数的系数还多上了 $\binom{n}i{}$。从排列组合的角度理解，说明不同元素之间相对顺序的改变会产生新的方案，或者说这样求出来的方案数是带标号的。

2.3 指数函数 exp

设 $\hat{F}(x)$ 为 $f_i$ 的 EGF，考虑 EGF $\hat{F}^k(x)$ 的意义，即 $k$ 个 $\hat{F}(x)$ 卷积得到：

$$\hat{F}^k(x)=\sum_{n\ge 0}\frac{x^n}{n!}n!\sum_{\sum_i^k a_i=n}\prod_{j}^k\frac{f_{a_j}}{a_j!}$$

从集合的角度理解就是将 $n$ 个有标号元素划分到 $k>0$ 个有标号集合中。$n=0$ 时系数为多项式常数项的乘积，之后的多项式 $\exp$ 的常数项需要满足常数项为 $0$。

设 $F_k(n)$ 为 $n$ 个有标号元素划分为 $k$ 非空无序集合（这里 $n,k$ 的意义与上面相反，非空因为 $\exp$ 要求常数项为 $0$），$f_n$ 为满足原有 $n$ 个元素组成的特定结构的数量（具体由求解问题给定，且只与集合个数 $n$ 相关）。根据定义得到：

$$\begin{align} F_k(n)=\frac{n!}{k!}\sum_{\sum_i^k a_i=n}\prod_{j}^k\frac{f_{a_j}}{a_j!}\notag\\ \end{align}$$

设 $F_k(n)$ 的 EGF 为 $G(x)$，那么得到：

$$\begin{align} G_k(x)&=\sum_{n\ge 0}\frac{x^n}{n!}F_k(n)\notag\\ G_k(x)&=\frac{1}{k!}\sum_{n\ge 0}x^n\sum_{\sum_i^k a_i=n}\prod_{j}^k\frac{f_{a_j}}{a_j!}\notag\\ G_k(x)&=\frac{1}{k!}\hat{F}^k(x) \end{align}$$

我们得到 $G_k$，尝试对 $G$ 求和得到 $G$：

$$G(x)=\sum_{k\ge 0} G_k(x)=\sum_{k\ge 0}\frac{1}{k!}\hat{F}^k(x)=\exp \hat{F}(x)$$

$\hat{F}(x)$ 是 $f_n$ 的指数生成函数，$f_n$ 为满足原有 $n$ 个元素组成的特定结构的数量。于是我们得到指数函数 $\exp$ 即 $G(x)=\exp \hat{F}(x)$ 的组合意义：表示将 $n$ 个元素划分为任意个不为空的集合的方案数。这就是指数公式定理。形式化的描述，即：

如果存在两个 EGF $F(x),G(x)$，其中 $F(x)$ 为 $f_n$ 的 EGF，$G(X)=\exp F(x)$，那么 $G(x)$ 是：

$$g_n=\sum_{\pi={S_1,S_2,\cdots,S_k}}\prod_{i=1}^k f_{|S_i|}$$

的 EGF，$\pi$ 是 $[n]$ 的一个划分。

2.4 例题

1.P4841 [集训队作业2013]城市规划

设 $f_n$ 表示 $n$ 个点的有标号无向连通图方案数，$g_n$ 表示 $n$ 个点的有标号无向图方案数，$F(x),G(x)$ 分别为二者的 EGF。首先容易得到：$g_n=2^{\binom{n}{2}}$。

根据指数公式定理，我们容易得到：

$$\exp F(x)=G(x)$$

于是我们只需要对 $G(x)$ 取 $\ln$ 即可得到 $F(x)=\ln G(x)$。