生成函数：从入门到出门
普通生成函数
定义
序列 $a$ 的普通生成函数定义为：$\displaystyle F(x)=\sum_{n}a_n x^n$。
$a$ 既可以是有穷序列，也可以是无穷序列。
举些例子:
- 序列 $a=\langle 1,2,3\rangle$ 的普通生成函数是 $1+2x+3x^2$。
- 序列 $a=\langle 1,1,1,\cdots\rangle$ 的普通生成函数是 $\displaystyle \sum_{n\ge 0}x^n$。
- 序列 $a=\langle 1,2,4,8,16,\cdots\rangle$ 的生成函数是 $\displaystyle \sum_{n\ge 0}2^nx^n$。
可以发现，（对有通项公式的函数）它的普通生成函数的系数就是通项公式。
运算
加减
对于序列 $a,b$ 的普通生成函数，分别为 $F(x),G(x)$。那么有
$$
F(x)\pm G(x)=\sum_{n\ge 0} (a_n\pm b_n)x^n
$$
因此 $$F(x)\pm G(x)$$ 是序列 $$\displaystyle\langle a_n\pm b_n\rangle$$ 的普通生成函数。
乘
考虑乘法（卷积）：
$$
F(x)G(x)=\sum_{n\ge 0} x^n \sum_{i=0}^na_ib_{n-i}
$$
因此 $F(x)G(x)$ 是序列 $\displaystyle \langle \sum_{i=0}^n a_ib_{n-i} \rangle$ 的普通生成函数。
看着眼熟吗，没错，就是多项式乘法的系数通项。
运算律
满足结合律，交换律，分配率。
应用
假设有 $n$ 物品，它们分别有一些数量，求从其中选出 $k$ 件物品，不考虑顺序（多重集排列），求方案数。
每件物品有种选定的规则（例如偶数个，奇数个，$4$ 的倍数个，特定个数个等），但是我们先对每个物品构造一个多项式函数，其中第 $i$ 项的系数 $a_i$ 表示选了 $i$ 个当前物品的方案数。
例如什么规则都没有，那么 $\forall i \isin [1,n],a_i=1$（当然没有限制就是一种），又比如只有在 $10$ 以内的偶数，生成函数对应的序列就是 $\displaystyle \langle 1，0,1,0,1,0,1,0,1,0,1,0,0,0,0,\cdots \rangle$。
然后我们将这些生成函数乘起来（卷积起来），对应 $x^k$ 项的系数就是答案，具体证明参见背包问题的多重背包。
指数生成函数
定义
序列 $a$ 的指数生成函数定义为：$\displaystyle F(x)=\sum_{n}a_n \frac{x^n}{n!}$。
运算
指数生成函数的加减法与普通生成函数是相同的，也就是对应项系数相加。
乘法（卷积）
对于两个序列 $a,b$，设它们的指数生成函数分别为
$F(x),G(x)$，那么
$$
\begin{aligned}
F(x)G(x)
&=\sum_{i\ge 0}a_i\frac{x^i}{i!}\sum_{j\ge 0}b_j\frac{x^j}{j!}\
&=\sum_{n\ge 0}x^{n}\sum_{i=0}^na_ib_{n-i}\frac{1}{i!(n-i)!}\
&=\sum_{n\ge 0}\frac{x^{n}}{n!}\sum_{i=0}^n\binom{n}{i}a_ib_{n-i}
\end{aligned}
$$
因此 $F(x)G(x)$ 是序列 $\displaystyle\left\langle \sum_{i=0}^n \binom{n}{i}a_ib_{n-i} \right\rangle$ 的指数生成函数。
应用
指数生成函数（Exponential Generating Function, EGF）在信息学竞赛中主要用于以下场景：
-
排列计数：
- 用于计算不同排列的数量，特别是涉及元素重复或特定限制的排列问题。
- 典型问题：计算有重复元素的排列数、受限排列（如不相邻元素）。
-
组合计数：
- 处理组合问题时，尤其是在有重复元素或特定限制的情况下。
- 典型问题：多重集合的组合、有限制的子集选择。
-
生成递推关系：
- 通过生成函数将复杂的递推关系转化为简单的代数形式，便于求解。
- 典型应用：求解递推数列、动态规划优化。
-
多项式乘法优化：
- 利用生成函数的乘法性质，快速计算组合或排列问题的解。
- 典型应用：FFT加速多项式乘法，提升计数效率。
-
特殊数列与组合结构：
- 用于分析斯特林数、贝尔数等组合数列的性质。
- 典型应用：划分问题、集合划分与排列的关系。
总结：指数生成函数是信息学竞赛中处理排列、组合及递推问题的重要工具，能简化复杂问题并提升效率。
$\small{以上内容为 AI 生成，请注意辨别真伪}$
举个例子，就把原来的排列变成组合，是不是就完全一样的推导过程了。
例如，对于一个多重集 $(S = {n_1 \cdot a_1, n_2 \cdot a_2, \ldots, n_k \cdot a_k})$，多重集 $(S)$ 的 $®$ 排列数可以通过对应的指数生成函数来求解。这个生成函数 $(G_e(x))$ 是由每个生成函数项 $(f_{n_i}(x))$ 相乘得到的，其中 $(f_{n_i}(x))$ 定义为： $[f_{n_i}(x) = 1 + x + \frac{x^2}{2!} + \ldots + \frac{x^{n_i}}{n_i!}]$ 将 $(G_e(x))$ 展开后，其中的 $(r!x^r)$ 的系数就是多重集的 $®$ 排列数。
狄利克雷生成函数
定义
还是那样：$\displaystyle F(x) = \sum_{i\ge 1}\frac{f_i}{i^x}$。
运算
加减不用说了。
对于两个数论函数 $f(x)$ 和 $g(x)$，则它们的狄利克雷卷积得到的结果 $h(x)$ 定义为：
$$
h(x)=\sum_{d\mid x}{f(d)g\left(\dfrac xd \right)}=\sum_{ab=x}{f(a)g(b)}
$$
狄利克雷卷积与狄利克雷生成函数密切相关。对于两个序列 $f, g$，其狄利克雷生成函数之积，对应的是两者的狄利克雷卷积序列的狄利克雷生成函数：
$$
F(x)G(x) = \sum_{i} \sum_{j}\frac{f_i g_j}{(ij)^x} = \sum_{i} \frac{1}{i^x}\sum_{d | i} f_d g_{\frac{i}{d}}
$$
应用
主要用于各种函数的变形。