指数生成函数

序列的指数生成函数（exponential generating function，EGF）定义为形式幂级数：

\hat{F}(x)=\sum_{n}a_n \frac{x^n}{n!}

基本运算

指数生成函数的加减法与普通生成函数是相同的，也就是对应项系数相加。

考虑指数生成函数的乘法运算。对于两个序列，设它们的指数生成函数分别为 $\hat{F}(x),\hat{G}(x)$ ，那么

\begin{aligned} \hat{F}(x)\hat{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}

因此 $\hat{F}(x)\hat{G}(x)$ 是序列

\left\langle \sum_{i=0}^n \binom{n}{i}a_ib_{n-i} \right\rangle

的指数生成函数。

封闭形式

我们同样考虑指数生成函数的封闭形式。

序列 $\langle 1,1,1,\cdots\rangle$ 的指数生成函数是：

\hat{F}(x) = \sum_{n \ge 0}\frac{x^n}{n!} = \mathrm{e}^x

因为你将 $\mathrm{e}^x$ 在处泰勒展开就得到了它的无穷级数形式。

类似地，等比数列 $\langle 1,p,p^2,\cdots\rangle$ 的指数生成函数是：

\hat{F}(x) = \sum_{n\ge 0}\frac{p^nx^n}{n!}=\mathrm{e}^{px}

指数生成函数与普通生成函数

如何理解指数生成函数？我们定义序列的指数生成函数是：

F(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!}

但实际上也是序列 $\left\langle \dfrac{a_n}{n!} \right\rangle$ 的普通生成函数。

这两种理解没有任何问题。也就是说，不同的生成函数只是对问题理解方式的转变。

EGF 中多项式 exp 的组合意义

如果您还没有学习多项式 exp 请先跳过这里，这是由 exp 理解引出的意义，从某种意义上来说可以加深对 EGF 的理解。

EGF 中的默认是一个 EGF，那么我们首先考虑任意两个 EGF 的乘积

\hat{H}(x) = \hat{F}(x)\hat{G}(x) = \sum_{n\geq 0} \left[ \sum_{i = 0}^n\binom {n}{i}f_ig_{n-i} \right] \frac{x^n}{n!}

对于两个 EGF 相乘得到的 $[x^k]\hat{H}(x)$ ，实际上是一个卷积。而如果考虑多个 EGF 相乘得到的 $[x^k]\hat{H}(x)$ ，实际上就是对每个 EGF 选择一项 $x^{a_i}$ 使得 $\sum_ia_i=k$ 时每种情况系数的和。从集合的角度来理解就是把个有标号元素划分为个有标号集合的方案数。

如果则系数显然为原 EGF 各项常数的积，但是多项式 $\exp$ 中某些要求导致 $\exp$ 的常数项必须为，具体的原因在下文中会做出一些说明。

多项式系数定义（具体请参考排列组合一栏中的多项式系数组合意义）里是默认集合有序的，但是 $\exp(f(x))$ 中，个相乘得到的 EGF 相同，而集合划分显然是无序的，因此其系数应该乘上 $\dfrac{1}{k!}$ 。

设为个有标号元素划分成个非空无序集合（因为是 $\exp$ 所以有非空要求）的情况，为个元素组成一个集合时，个元素的有限集上特定组合结构的数量（是原有的 EGF，对这一个集合元素计数的方案，仅仅与该集合大小有关），那么

F_k(n)=\frac{n!}{k!}\sum_{\sum_{i}^ka_i=n}\prod_{j=1}^{k}\frac{f_{a_j}}{a_j!}

设的 EGF 为 $\hat{F}(x)$ ，即：

\hat{F}(x) = \sum_{n \geq 0} f_n\frac{x^n}{n!}

设的 EGF 为，则：

\begin{aligned} G_k(x)&=\sum_{n \geq 0} F_k(n)\frac{x^n}{n!}\\ &=\sum_{n \geq 0} x^n\frac{1}{k!}\sum_{\sum_i^k a_i=n}\prod_{j=1}^{k}\frac{f_{a_j}}{a_j!}\\ &=\frac{1}{k!}\sum_{n \geq 0}\sum_{\sum_i^k a_i=n}\prod_{j=1}^{k}\frac{f_{a_j}x^{a_j}}{a_j!}\\ &=\frac{1}{k!}\hat{F}^k(x) \end{aligned}

对于所有的 $k \geq 0$ ：

\sum_{k \geq 0}G_k(x) = \sum_{k \geq 0}\frac{\hat{F}^k(x)}{k!} = \exp{\hat{F}(x)}

上面是从组合角度直接列式理解，我们也可以从递推方面来证明 $\exp(f(x))$ 和两者间的关系。

同样设为个有标号元素划分成个非空集合（无标号）的情况，为个元素组成一个集合内部的方案数（意义同上文中的），并令为 $\{g_i\}$ 的 EGF，为 $\{F_k(n)\}$ 的 EGF。

个元素中取出个元素作为一个单独划分出去的集合共有种方案，剩下的个元素构成个集合共 $F_{k-1}(n-i)$ 种方案，但最后的划分方案中，一个方案里的每个集合都会被枚举为单独划分出去的集合，所以重复计算了次，故还需要除以。

\begin{aligned} H_k(x) &= \sum_{n\ge 0}\cfrac{x^n}{n!}F_k(n)\\ &=\sum_{n\ge 0}\cfrac{x^n}{n!}\sum_{i=1}^{n-k+1}\binom n {i} F_{k-1}(n-i)\times g_i\times \cfrac{1}{k}\\ &=\cfrac{1}{k}\sum_{n\ge 0}\cfrac{x^n}{n!}\sum_{i=0}^{n}\binom n {i}F_{k-1}(n-i)\times g_i\\ &=\cfrac{1}{k}\cdot H_{k-1}(x)G(x) \end{aligned}

上界是由非空集合划分推出的 $n-(k-1)\geq i$ （前个集合每个集合最少有一个元素），但是如果超过枚举上界涉及的 $F_{k-1}(n-i)$ 设为，那么就没有影响。

得到递推式之后可递归展开，边界为时。

\begin{aligned} H_k(x) &= \cfrac{1}{k}\cdot H_{k-1}(x)G(x)\\ &= \cfrac{1}{k}\cdot\cfrac{1}{k-1}\cdot H_{k-2}(x)G^2(x)\\ &=\cdots \\ &= \cfrac{1}{k}\cdot\cfrac{1}{k-1} \cdots\cfrac{1}{2}\cdot H_{1}(x)G^{k-1}(x)\\ &= \cfrac{1}{k!}G^{k}(x)\\ \end{aligned}

同样的有：

\begin{aligned} \sum_{k\ge 0}H_k(x)=\sum_{k\ge 0}\cfrac{G^k(x)}{k!}=\exp G(x) \end{aligned}

显然 定义成划分为非空集合（）是符合本身的意义的，如果 包含空集（），那么对应中就会有的贡献（在至少一个中选择常数项），有计重，得不到所求量。

从递推式的角度讲，多个 EGF 的乘积也可以看作一个类似于背包的组合（合并两组计数对象的过程）。

总结多项式 $\exp$ 的意义就是：有标号元素构成的集合的生成集族有多少种情况，或划分为任意个非空子集的总方案数。

排列与圆排列

长度为的排列数的指数生成函数是

\hat{P}(x)=\sum_{n\ge 0}\frac{n!x^n}{n!}=\sum_{n\ge 0}x^n=\frac{1}{1-x}

圆排列的定义是把 $1,2,\cdots,n$ 排成一个环的方案数。也就是说旋转后的方案的等价的（但翻转是不等价的）。

个数的圆排列数显然是。因此个数的圆排列数的指数生成函数是

\hat{Q}(x)=\sum_{n\ge 1}\frac{(n-1)!x^n}{n!}=\sum_{n\ge 1}\frac{x^n}{n}=-\ln(1-x)=\ln\left( \frac{1}{1-x} \right)

也就是说 $\exp \hat{Q}(x)=\hat{P}(x)$ 。但这只是数学层面的推导。我们该怎样直观理解：圆排列数的 EGF 的 $\exp$ 是排列数的 EGF？

一个排列，是由若干个置换环构成的。例如有两个置换环：

（也就是说我们从向连有向边）

而不同的置换环，会导出不同的排列。例如将第二个置换环改成

那么它对应的排列就是。

也就是说，长度为的排列的方案数是

把 $1,2,\cdots,n$ 分成若干个集合
每个集合形成一个置换环

的方案数。而一个集合的数形成置换环的方案数显然就是这个集合大小的圆排列方案数。因此长度为的排列的方案数就是：把 $1,2,\cdots,n$ 分成若干个集合，每个集合的圆排列方案数之积。

这就是多项式 $\exp$ 的直观理解。

推广之

如果个点 带标号 生成树的 EGF 是 $\hat{F}(x)$ ，那么个点 带标号 生成森林的 EGF 就是 $\exp \hat{F}(x)$ ——直观理解为，将个点分成若干个集合，每个集合构成一个生成树的方案数之积。
如果个点带标号无向连通图的 EGF 是 $\hat{F}(x)$ ，那么个点带标号无向图的 EGF 就是 $\exp \hat{F}(x)$ ，后者可以很容易计算得到
$\exp \hat{F}(x)=\sum_{n\ge 0}2^{\binom{n}{2}}\frac{x^n}{n!}$
因此要计算前者，只需要一次多项式 $\ln$ 即可。

接下来我们来看一些指数生成函数的应用。

应用

错排数

定义长度为的一个错排是满足 $p_i\ne i$ 的排列。

求错排数的指数生成函数。

从置换环的角度考虑，错排就是指置换环中不存在自环的排列。也就是说不存在长度为的置换环。后者的指数生成函数是

\sum_{n\ge 2}\frac{x^n}{n}=-\ln\left(1-x\right)-x

因此错排数的指数生成函数就是 $\exp(-\ln(1-x)-x)$ 。

不动点

题意：求有多少个映射 $f:\{1,2,\cdots,n\}\to \{1,2,\cdots,n\}$ ，使得

\underbrace{f\circ f\circ\cdots\circ f}_{k}=\underbrace{f\circ f\circ\cdots\circ f}_{k-1}

$nk\le 2\times 10^6,1\le k\le 3$ 。

考虑向连边。相当于我们从任意一个走步和走步到达的是同一个点。也就是说基环树的环是自环且深度不超过（根结点深度为）。把这个基环树当成有根树是一样的。因此我们的问题转化为：个点带标号，深度不超过的有根树森林的计数。

考虑个点带标号深度不超过的有根树，假设它的生成函数是：

\hat{F_k}(x)=\sum_{n\ge 0}f_{n,k}\frac{x^n}{n!}

考虑递推求 $\hat{F_k}(x)$ 。深度不超过的有根树，实际上就是深度不超过的若干棵有根树，把它们的根结点全部连到一个结点上去。因此

\hat{F_k}(x)=x\exp \hat{F}_{k-1}(x)

那么答案的指数生成函数就是 $\exp \hat{F}_k(x)$ 。求它的第项即可。

Lust

给你一个个数的序列 $a_1,a_2,\cdots,a_n$ ，和一个初值为的变量，要求你重复以下操作次：

在 $1,2,\cdots,n$ 中等概率随机选择一个。
令加上 $\prod_{i\ne x}a_i$ 。
令减一。

求次操作后的期望。

$1\le n\le 5000,1\le k\le 10^9,0\le a_i\le 10^9$ 。

假设次操作后减少了，那么实际上

s=\prod_{i=1}^n a_i-\prod_{i=1}^n(a_i- b_i)

因此实际上我们的问题转化为，求次操作后 $\prod_{i=1}^n (a_i- b_i)$ 的期望。

不妨考虑计算每种方案的的 $\prod_{i=1}^n (a_i- b_i)$ 的和，最后除以。

而次操作序列中，要使得出现了次的方案数是

\frac{k!}{b_1!b_2!\cdots b_n!}

这与指数生成函数乘法的系数类似。

设的指数生成函数是

F_j(x)=\sum_{i\ge 0}(a_j-i)\frac{x^i}{i!}

那么答案就是

[x^k]\prod_{j=1}^nF_j(x)

为了快速计算答案，我们需要将转化为封闭形式：

\begin{aligned} F_j(x)&=\sum_{i\ge 0}a_j\frac{x^i}{i!}-\sum_{i\ge 1}\frac{x^i}{(i-1)!}\\ &=a_j\mathrm{e}^x-x\mathrm{e}^x\\ &=(a_j-x)\mathrm{e}^x \end{aligned}

因此我们得到

\prod_{j=1}^nF_j(x)=\mathrm{e}^{nx}\prod_{j=1}^n(a_j-x)

其中 $\prod_{j=1}^n(a_j-x)$ 是一个次多项式，可以暴力计算出来。假设它的展开式是 $\sum_{i=0}^nc_ix^i$ ，那么

\begin{aligned} \prod_{j=1}^nF_j(x) &=\left(\sum_{i\ge 0} \frac{n^ix^i}{i!}\right)\left(\sum_{i=0}^nc_ix^i\right)\\ &=\sum_{i\ge 0}\sum_{j=0}^i c_jx^j\frac{n^{i-j}x^{i-j}}{(i-j)!}\\ &=\sum_{i\ge 0}\frac{x^{i}}{i!}\sum_{j=0}^i n^{i-j}i^{\underline{j}}c_j \end{aligned}

计算这个多项式的项系数即可。

本页面最近更新：2023/9/1 16:49:46，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：sshwy, ComeIntoCalm, countercurrent-time, Early0v0, Enter-tainer, GhostLX-AI, Great-designer, NachtgeistW, shuzhouliu, SukkaW, Tiphereth-A, untitledunrevised
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用