生成函数：从入门到出门

普通生成函数

定义

序列 $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）在信息学竞赛中主要用于以下场景：

1. 排列计数：

   • 用于计算不同排列的数量，特别是涉及元素重复或特定限制的排列问题。
   • 典型问题：计算有重复元素的排列数、受限排列（如不相邻元素）。

2. 组合计数：

   • 处理组合问题时，尤其是在有重复元素或特定限制的情况下。
   • 典型问题：多重集合的组合、有限制的子集选择。

3. 生成递推关系：

   • 通过生成函数将复杂的递推关系转化为简单的代数形式，便于求解。
   • 典型应用：求解递推数列、动态规划优化。

4. 多项式乘法优化：

   • 利用生成函数的乘法性质，快速计算组合或排列问题的解。
   • 典型应用：FFT加速多项式乘法，提升计数效率。

5. 特殊数列与组合结构：

   • 用于分析斯特林数、贝尔数等组合数列的性质。
   • 典型应用：划分问题、集合划分与排列的关系。

总结：指数生成函数是信息学竞赛中处理排列、组合及递推问题的重要工具，能简化复杂问题并提升效率。

$\small{以上内容为 AI 生成，请注意辨别真伪}$

举个例子，就把原来的排列变成组合，是不是就完全一样的推导过程了。

例如，对于一个多重集 $(S = {n_1 \cdot a_1, n_2 \cdot a_2, \ldots, n_k \cdot a_k})$，多重集 $(S)$ 的 $(r)$ 排列数可以通过对应的指数生成函数来求解。这个生成函数 $(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)$ 的系数就是多重集的 $(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}}$$

应用

主要用于各种函数的变形。