指数生成函数入门笔记
wanganze
·
·
算法·理论
引言
参考了 oi-wiki。
普通生成函数介绍。
当问题涉及排列、顺序或带标号的对象时，普通生成函数（OGF）往往力不从心。这时就要指数生成函数（EGF）出场了。
本文所有无穷级数均视为形式幂级数，只关心系数运算，不讨论收敛性。
指数生成函数的定义
实数序列 a_0,a_1,\cdots,a_k,\cdots 的指数生成函数是无穷级数
\hat G(x)=a_0+a_1\frac{x}{1!}+a_2\frac{x^2}{2!}+\dots+a_k\frac{x^k}{k!}+\dots=\sum_{k=0}^{\infty}a_k\frac{x^k}{k!}
和 OGF 同样，对于一个长度为 n+1 的有限序列 a_0,a_1,\dots,a_n，我们可以通过置 a_{n+1}=0,a_{n+2}=0,\cdots 把一个有限的序列扩充成一个无限的序列（后面补零），这样就可以定义一个实数的有限序列的指数生成函数。
现在看这种定义带来了什么变化。相比普通生成函数，指数生成函数在每一项多除以了 n!，它恰好抵消了排列中的顺序计数，使得 EGF 的乘法运算自然地对应二项式卷积。
具体地，EGF 的乘法运算如下：
设序列 \{a_n\}、\{b_n\} 的 EGF 分别为 \hat F(x)、\hat G(x)，则
\hat F(x)\hat G(x)
&=\sum_{i=0}^{\infty}a_i\frac{x^i}{i!}\sum_{j=0}^{\infty}b_j\frac{x^j}{j!}\\
&=\sum_{n=0}^{\infty}x^n\sum_{i=0}^n a_i b_{n-i}\frac{1}{i!(n-i)!}\\
&=\sum_{n=0}^{\infty}\frac{x^n}{n!}\sum_{i=0}^nC_n^ia_i b_{n-i}
\end{aligned}
因此，\hat F(x)\hat G(x) 是序列 c_n=\sum_{i=0}^nC_n^ia_i b_{n-i} 的指数生成函数。
指数生成函数的乘法包含了二项式系数，这说明了 EGF 能自动处理排列问题。这样我们在列方程时，只需要像普通乘法一样把因子乘起来，二项式选取自然就被算进去了，不用额外考虑组合数。
理解：先从 n 个有标号的元素中选出 i 个分配给 A，剩下 n-i 个分配给 B。选法有 C_n^i 种。在选出的 i 个元素上构造 A 结构，有 a_i 种。在剩下的元素上构造 B 结构，有 b_{n-i} 种。
几个有用的指数生成函数
| ::cute-table{tuack} |
\hat F(x) |
a_n |
备注 |
| e^x=\sum\limits_{n=0}^{\infty}\frac{x^n}{n!} |
1 |
根据定义 |
| e^{ax}=\sum\limits_{n=0}^{\infty}\frac{a^n x^n}{n!} |
a^n |
等比数列，代换上式变量即可 |
| \frac{e^x+e^{-x}}2=\sum\limits_{n=0}^{\infty}\frac{x^{2n}}{(2n)!} |
[2\mid n]（n 为偶数时为 1，否则为 0） |
这个和下一条可以一起证明，利用 e^x 与 e^{-x} 相加、相减得到（具体见下一格） |
| \frac{e^x-e^{-x}}2=\sum\limits_{n=0}^{\infty}\frac{x^{2n+1}}{(2n+1)!} |
[2\nmid n]（n 为奇数时为 1，否则为 0） |
e^x 对应全 1 序列，e^{-x} 对应序列 (-1)^n |
| \frac{1}{1-x}=\sum\limits_{n=0}^{\infty}n!\frac{x^n}{n!} |
n! |
就是全排列 A_n^n=n!，证明直接展开 |
| -\ln(1-x)=\sum\limits_{n=1}^{\infty}(n-1)!\frac{x^n}{n!} |
(n-1)! |
圆排列 \frac{A_n^n}{n}=(n-1)!，泰勒展开可证 |
EGF 求解排列计数问题
例题 1
EGF 可以求解多重集的排列，类似于 OGF 解决多重集的组合。
用数字 1,2,3,4 组成五位数，要求数字 1 出现次数在 1\sim3 之间，数字 2 出现次数 \le 2，数字 3,4 出现次数 \le 1，求方案数。
和 OGF 一样，每种数字（对象）对应一个因子。因子中 x^n 的系数为 \frac1{n!}（因为同种数字内部交换顺序不产生新排列），所以我们可以写出下面的生成函数：
\hat G(x)=\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}\right)\left(1+x+\frac{x^2}{2!}\right)(1+x)^2
因为 \hat G = \sum_{k=0}^{\infty}a_k\frac{x^k}{k!}，我们展开并提取 x^5 的系数 \dfrac{a_5}{5!}，乘以 5! 后得到的就是实际方案数 a_5。
因此 a_5 = \frac{25}{12}\times 5!= 250。
所以满足条件的五位数共有 250 个。
例题 2
AT_fps_24_f。
求由颜色 a,b,c 组成的长度为 n 的序列中，a 出现奇数次、b 出现偶数次的方案数。
每个颜色是一个对象，对应一个因子：a 对应 \frac{e^x-e^{-x}}2，b 对应 \frac{e^x+e^{-x}}2，c 就对应 e^x。
所以写出生成函数，答案就是 x^n 的系数乘上 n!。
\begin{aligned}
\hat G(x)&=\frac{e^x-e^{-x}}2\times\frac{e^x+e^{-x}}2\times e^x\\
&=\frac{e^{2x}-e^{-2x}}4\times e^x\\
&=\frac{e^{3x}-e^{-x}}4\\
&=\frac14\sum_{n=0}^{\infty}3^n\frac{x^n}{n!}-\frac14\sum_{n=0}^{\infty}(-1)^n\frac{x^n}{n!}\\
&=\sum_{n=0}^{\infty}\frac{3^n-(-1)^n}{4}\times\frac{x^n}{n!}
\end{aligned}
所以方案数 a_n=\dfrac{3^n-(-1)^n}{4}。
指数生成函数 \exp 的理解
这里我们考虑经典的错排问题。首先可以发现，错排由若干个长度 \ge2 的置换环组成。
我们知道长度为 n 的圆排列数为 (n-1)!，其 EGF 为 -\ln(1-x)。去掉长度为 1 的圆排列（自环），我们得到长度 \ge2 的置换环的生成函数 \hat G(x)=-\ln(1-x)-x。我们现在的问题就是把 n 个有标号元素划分成若干个无序的置换环集合。
枚举置换环的个数 k。如果我们先按顺序排列这 k 个环，则每个划分会被重复计数 k! 次（因为环之间没有顺序），因此最后需要除以 k!。那么划分为 k 个有序置换环的方案数的生成函数 \hat G(x)^k。为了消去这些置换环的顺序（划分不考虑顺序），我们除掉 k!，这样我们就得到了最终的方案数的生成函数 \hat F_k(x)=\frac{\hat G(x)^k}{k!}。
因为不同 k 的情况互斥，我们对 k=0,1,2,\dots 求和，得到如下生成函数：
\hat F(x)=\sum_{k=0}^{\infty} \hat F_k(x)=\sum_{k=0}^{\infty} \frac{\hat G(x)^k}{k!}
这不就是我们 \exp 的泰勒展开吗？如果把上面叙述中的置换环换成一般的结构，我们就这样推导出了多项式 \exp 的组合意义：
若某类非空有标号结构的 EGF 为 \hat G(x)（\hat G(0)=0），那么由任意数量（可为0）这类结构组成的集合（无序）的 EGF 为 \exp(\hat G(x))。
所以，错排的生成函数为 \exp(-\ln(1-x)-x)=\frac{e^{-x}}{1-x}。
\begin{aligned}
\sum_{n=0}^{\infty} \frac{D_n}{n!} x^n&=\frac{e^{-x}}{1-x}\\
&=\left(\sum_{i=0}^{\infty}(-1)^i\frac{x^i}{i!}\right)\left(\sum_{j=0}^{\infty}j!\frac{x^j}{j!}\right)\\
&=\sum_{n=0}^{\infty} \left( \sum_{i=0}^{n} (-1)^i \frac{x^i}{i!} \times x^{n-i} \right)\\
&=\sum_{n=0}^{\infty} \left( \sum_{i=0}^{n} \frac{(-1)^i}{i!}\right) x^n
\end{aligned}
所以 D_n=n!\sum\limits_{i=0}^{n} \frac{(-1)^i}{i!}。
小结
回顾全文，指数生成函数的核心思想可以概括为：通过预先在定义中除以 n!，将排列计数的负担从组合数的计算中转移给形式幂级数的代数运算自动处理。
这篇文章虽然没有涉及更复杂的递推或多项式算法，但通过几个典型例子已经展示了 EGF 的基本用法：与 OGF 一样，“构造级数，提取系数”。
读完并理解本文，或许你已经入门了生成函数，这两篇笔记的任务也就达到了。