Generating Function (I)

形式幂级数 $A(x)=\sum_{i \geq 0} a_i x^i$ ，其中 $a_i \in K, K$ 是一个域。

形式幂级数在 $+,-,\times$ 下形成一个环（定义类比多项式）。

记形式幂级数或多项式 $A(x)$ 的 $x^n$ 项的系数为 $\left[x^n\right] A(x)$ 。

Ordinary generating function (OGF)

一个数列 $\{a_n\}$ 对应的常生成函数 (Oridinary Generating Function) 为 $A(x)=\sum_{n \geq 0} a_n x^n$ 。

到计数问题中，$a_nx^n$ 中指数 $n$ 代表选择 $n$ 个物品，系数 $a_n$ 代表选 $n$ 个物品的方案数。

设 $S=\{a_1, a_2, \ldots, a_k\}$，且 $a_i$ 可以取的次数的集合为 $M_i$，常生成函数 $F_i(x)=\sum_{u \in M_i} x^u$。

则从 $S$ 中取 $n$ 个元素组成集合的方案数 $g(n)$ 的常生成函数 $G(x)=\sum_{i \geq 0} g(i) x^i$，满足
$$
G(x)=F_1(x) F_2(x) \ldots F_k(x)
$$

证明从多项式乘法对应的系数相乘，指数相加的角度理解即可。

形式幂级数 $A(x)$ 的逆元 $B(x)$ 满足 $A(x) B(x)=1$，通常用来化简生成函数相乘。

因为两个多项式的乘积常数项只能来自两个多项式的常数项，因此逆元存在的条件是 $\left[x^0\right] A(x) \neq 0$ 。

暴力求多项式的逆元直接做多项式除法即可，注意逆元可能是有穷项的，也可能是无穷项的。

• $A(x)=1+x+x^2+\ldots$ 和 $B(x)=1-x$, 即 $\frac{1}{1-x}=\sum_{i \geq 0} x^i$
• $A(x)=\binom{k-1}{0}+\binom{k}{1} x+\binom{k+1}{2} x^2+\binom{k+2}{3} x^3+\ldots$ 和 $B(x)=(1-x)^k$, 即 $\frac{1}{(1-x)^k}=\sum_{i \geq 0}(\stackrel{i+k-1}{i}) x^i$

第一个可以对 $x$ 进行换元。

第二个只需要证明 $A(x)=(1+x+x^2+\cdots)^k$ 即可，考虑 $[x^n] (1+x+x^2+\cdots)^k$ 的含义，相当于 $n$ 个球放入 $k$ 个框，球没有编号，框有编号。因此方案数插板是 ${k-1+n\choose n}$ 恰好对应于 $[x^n]A(x)$ 。

有限项的逆元可以配形如 $(1-x)$ 的多项式乘上去。

例题：[CF451E] Devu and Flowers, [CEOI2004] Sweets

递推关系：从数列的递推公式导出生成函数进而得到通项。

写出来生成函数 $A(x)$，对系数使用递推公式展开，将两侧都整理成和 $A(x)$ 相关的形式，解方程。

Exponential generating function (EGF)

一个数列 $\{a_n\}$ 对应的指数生成函数 (Exponential Generating Function) 为 $A(x)=\sum_{n \geq 0} a_n \frac{x^n}{n!}$ 。

到计数问题中，$a_nx^n$ 中指数 $n$ 代表选择 $n$ 个物品，系数 $a_n$ 代表选 $n$ 个物品排成一列的方案数。

设 $S=\{a_1, a_2, \ldots, a_k\}$，且 $a_i$ 可以取的次数的集合为 $M_i$，指数生成函数 $F_i(x)=\sum_{u \in M_i} \frac{x^u}{u!}$ 。

则从 $S$ 中取 $n$ 个元素排成一列的方案数 $g(n)$ 的指数生成函数 $G(x)=\sum_{i \geq 0} g(i) \frac{x^i}{i!}$，满足
$$
G(x)=F_1(x) F_2(x) \ldots F_k(x)
$$

证明考虑每个元素分别取的次数是 $b_1,b_2,\cdots,b_k$，则使用多重集的排列数：
$$
g(n)=\sum_{b_1+b_2+\cdots+b_k=n} \frac{n!}{b_1!b_2!\cdots b_n!}
$$

那么考虑

$$
[x^n] (F_1(x) F_2(x) \ldots F_k(x))=\sum_{b_1+b_2+\cdots+b_k=n} \frac{1}{b_1!b_2!\cdots b_n!}x^n=\frac{g(n)}{n!}x^n
$$

因此 $F_1(x) F_2(x) \ldots F_k(x)=\sum_{i\ge 0}g(i)\frac{x^i}{i!}=G(x)$ 。

注意这一结论可以拓展到两个 EGF 卷积表示的就是对应的物品集混合后的 EGF。

$\exp (x)=1+x+\frac{x^2}{2!}+\ldots=\sum_{n \geq 0} \frac{x^n}{n!}$

可以对 $x$ 进行换元。可以通过 $\exp(x)$ 化简 EGF 的卷积。

灵活使用 $\exp(-x)$ ，例如 $\sum_{i\ge 0}\frac{x^{2i}}{(2i)!}=\frac{e^x+e^{-x}}{2}$ 和 $\sum_{i\ge 0} \frac{x^{2i+1}}{(2i+1)!}=\frac{e^x-e^{-x}}{2} $ 等。