生成函数：从入门到出门

普通生成函数

定义

序列 a 的普通生成函数定义为：F(x) = ∑_na_nxⁿ。

a 既可以是有穷序列，也可以是无穷序列。

举些例子:

• 序列 a = ⟨1, 2, 3⟩ 的普通生成函数是 1 + 2x + 3x²。
• 序列 a = ⟨1, 1, 1, ⋯⟩ 的普通生成函数是 ∑_n ≥ 0xⁿ。
• 序列 a = ⟨1, 2, 4, 8, 16, ⋯⟩ 的生成函数是 ∑_n ≥ 02ⁿxⁿ。

可以发现，（对有通项公式的函数）它的普通生成函数的系数就是通项公式。

运算

加减

对于序列 a, b 的普通生成函数，分别为 F(x), G(x)。那么有

F(x) ± G(x) = ∑_n ≥ 0(a_n ± b_n)xⁿ

因此 F(x) ± G(x) 是序列 ⟨a_n ± b_n⟩ 的普通生成函数。

乘

考虑乘法（卷积）：

$$ 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 以内的偶数，生成函数对应的序列就是 ⟨1，0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, ⋯⟩。

然后我们将这些生成函数乘起来（卷积起来），对应 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₁ ⋅ a₁, n₂ ⋅ a₂, …, n_k ⋅ a_k)，多重集 (S) 的 (r) 排列数可以通过对应的指数生成函数来求解。这个生成函数 (G_e(x)) 是由每个生成函数项 (f_ni(x)) 相乘得到的，其中 (f_ni(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}} $$

应用

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