笔记 数学 指数生成函数
指数生成函数
我们知道 $h_0,h_1,h_2,\cdots,h_n,\cdots$ 的普通生成函数（OGF）是
\[H(x)=h_0+h_1x+h_2x^2+\cdots+h_nx^n+\cdots\]现在我们来学习另一种生成函数——指数生成函数（EGF）。
$h_0,h_1,h_2,\cdots,h_n,\cdots$ 的指数生成函数是
我们为了区别普通生成函数和指数生成函数，在大写字母 $H(x)$ 顶上加个帽子变成 $\hat H(x)$ 用来表示指数生成函数。
如果 $h$ 是个恒定为 $1$ 的数列，即 $h_n=1$，那么其指数生成函数为
\[\hat H(x)=1+x+\frac{x^2}{2!}+\cdots+\frac{x^n}{n!}+\cdots\]根据泰勒展开的知识
\[\mathrm e^x=\sum_{i=0}^{\infty}\frac1{i!}x^i\]我们可以得到 $\hat H(x)$ 的封闭形式为 $\mathrm e^x$，这是一个指数函数，这就是指数生成函数名字的由来。
更一般的，数列
其生成函数的封闭形式就是 $\mathrm e^{ax}$，即
\[\mathrm e^{ax}=\sum_{i=0}^{\infty}\frac{a^i}{i!}x^i\]多重集合的排列数
总共有 $n$ 个球，共有 $k$ 种颜色，其中第 $i$ 种颜色的球有 $a_i$ 个，相同颜色的球没有任何区别。将其排成一行的方案数即为多重集合的排列数，记为
\[\binom n{a_1,a_2,\cdots,a_k}=\frac{n!}{a_1!a_2!\cdots a_k!}\]证明：假如每个球都是不同的，那么方案数就是全排列 $n!$。但是如果有颜色相同的球，会发现所有颜色相同的球均可任意进行交换，也就是说会有 $a_i!$ 种方案实际上是同一种，得除掉。对于每个颜色的球都除掉 $a_i!$，最后就得到有 $n!/a_1!a_2!\cdots a_k!$ 种方案。
多重集合的排列数还有另一种组合含义，这个含义和多重集合没啥关系，和排列没啥关系。
有 $n$ 个不同的球要放入 $k$ 个不同的盒子里，其中第 $k$ 堆的球必须有 $a_i$ 个。方案数也为多重集合的排列数，虽然和多重集合没啥关系，和排列也没啥关系。
证明：先从 $n$ 个球选出 $a_1$ 个放到第 $1$ 个盒子里，然后从剩余 $n-a_1$ 个球选出 $a_2$ 个放到第 $2$ 个盒子里，然后从剩余 $n-a_1-a_2$ 个球选出 $a_3$ 个放到第 $3$ 个盒子里……最后从剩余 $n-a_1-a_2-\cdots-a_{k-1}=a_k$ 个球选出 $a_k$ 个放到第 $k$ 个盒子里，那么根据乘法原理，方案数是
\[\binom{n}{a_1}\binom{n-a_1}{a_2}\binom{n-a_1-a_2}{a_3}\cdots\binom{n-a_1-a_2-\cdots-a_{k-1} }{a_k}\]展开组合数
\[\frac{n!}{a_1!(n-a_1)!}\frac{(n-a_1)!}{a_2!(n-a_1-a_2)!}\frac{(n-a_1-a_2)!}{a_3!(n-n-a_1-a_2-a_3)!}\cdots\frac{(n-a_1-a_2-\cdots-a_{k-1})!}{a_k!(n-a_1-a_2-\cdots-a_{k-1}-a_k)!}\]约分一下，得到答案是
\[\frac{n!}{a_1!a_2!\cdots a_k!}=\binom n{a_1,a_2,\cdots,a_k}\]利用指数生成函数可以生成多重集合的排列数的结构。
令 $\hat F_1(x)$ 表示把 $i$ 个格子染成蓝色的方案数的指数生成函数。显然 $F(x)$ 的每一项系数均为 $1/i!$，那么
令 $\hat F_2(x)$ 表示把 $i$ 个格子染成粉色的方案数的指数生成函数，但是我们有限制条件：我们至少染一个粉格子。显然 $\hat F(x)$ 的每一项系数均为 $1/i!$，除了第 $0$ 项的系数为 $0$。
\[\hat F_2(x)=\sum_{i=1}^{\infty}\frac1{i!}x^i=\mathrm e^x-1\]令 $\hat F_3(x)$ 表示把 $i$ 个格子染成白色的方案数的指数生成函数，但是我们有限制条件：我们只能染偶数数量的白格子。
这就有点麻烦了，我们必须让偶数次幂的系数为 $1/i!$，奇数次幂的系数为 $0$，还好我们记得 $\mathrm e^{-x}$ 的泰勒展开。
因此
\[\hat F_3(x)=\sum_{i=0}^{\infty}\frac{1+(-1)^i}{2\times i!}x^i=\frac{\mathrm e^x+\mathrm e^{-x} }2\]那么，$\hat G=\hat F_1\ast\hat F_2\ast\hat F_3$ 就是 $n$ 个格子染成蓝、粉、白的方案数，并且满足以下限制条件：
- 至少一个粉格子
- 偶数数量的白格子
证明：我们先不考虑这些限制条件，那么蓝、粉、白的指数生成函数都是 $\hat F_1$，其卷积就是 $\hat F_1^3=\hat F_1\ast\hat F_1\ast\hat F_1$。
由于指数生成函数也是一个多项式，那么我们不妨将其展开，记第一个 $\hat F_1$ 取到的指数为 $m_1$，第二个 $\hat F_1$ 取到的指数为 $m_2$，第三个 $\hat F_1$ 取到的指数为 $m_3$，那么
将几个阶乘放到一起，并且带入 $\hat F_1$
\[[x^n]\hat G=\sum_{m_1+m_2+m_3=n}\frac{n!}{m_1!m_2!m_3!}=\sum_{m_1+m_2+m_3=n}\binom{n}{m_1,m_2,m_3}\]这是一个多重集合的组合数，这相当于我们去枚举染成蓝、粉、白的格子数，然后把所有的情况加起来，其组合意义告诉我们这的确是 $n$ 个格子染成蓝、粉、白的方案数。
如果加上限制，那么
\[\frac{[x^n]\hat G(x)}{n!}=\sum_{m_1+m_2+m_3=n}\frac{[x^{m_1}]\hat F_1(x)}{m_1!}\frac{[x^{m_2}]\hat F_2(x)}{m_2!}\frac{[x^{m_3}]\hat F_3(x)}{m_3!}\]如果写成卷积形式，那就是 $\hat G=\hat F_1\ast\hat F_2\ast\hat F_3$。
不难证明，这些限制存在的情况下，其组合意义仍然正确，只不过不合法的系数都变成 $0$ 了。
和普通生成函数一样，我们用其封闭形式运算，最后再展开获得答案。
\[\begin{aligned} \hat G&=\hat F_1\ast\hat F_2\ast\hat F_3\\ &=\mathrm e^x(\mathrm e^x-1)\frac{\mathrm e^x+\mathrm e^{-x} }2\\ &=\frac{\mathrm e^{3x}-\mathrm e^{2x}+\mathrm e^{x}-1}{2}\\ &=-\frac12+\sum_{i=0}^\infty\frac{3^i-2^i+1}2\frac{x^i}{i!} \end{aligned}\]因此，$n$ 个格子染成蓝、粉、白的方案数，并且满足上述限制条件的方案数是：当 $n>0$ 时为$(3^n-2^n+1)/2$；当 $n=0$ 时，方案数为 $0$。
多项式 exp 的组合意义
如果您还没有学习多项式 $\exp$，甚至完全不会多项式，没有关系！多项式 $\exp$ 只不过是一种计算生成函数的工具，我们完全可以先从数学上学习多项式 $\exp$ 的组合意义。
根据上文多重集合的排列数，我们知道如果 $\hat H$ 是 $F,G$ 的卷积，$\hat H=\hat F\ast\hat G$，那么
\[\frac{h_n}{n!}=\sum_{i=0}^n\frac{f_i}{i!}\frac{g_{n-i} }{(n-i)!}\]如果把阶乘放在一起的话
\[h_n=\sum_{i=0}^n\binom nif_ig_{n-i}\]上述是指数生成函数的卷积形式。相比于普通生成函数
\[h_n=\sum_{i=0}^nf_ig_{n-i}\]来说，指数生成函数仿佛有一种分组的意味。我们接下来就要深入探讨指数生成函数的分组。
指数生成函数的 $\exp$ 仿佛就像一种反演。
- $\hat F(x)$ 表示 $n$ 个不同的球装进一个盒子里的方案数的生成函数。
- $\hat G(x)$ 表示 $n$ 个不同的球装进若干个相同的盒子里的方案数的生成函数。
那么
\[\hat G(x)=\exp\hat F(x)=\sum_{i=0}^\infty\frac1{i!}\hat F^i(x)\]模仿上面给格子染色，我们很快就可以写出其表达式。
首先枚举盒子的数量 $k$，然后再枚举每个盒子放的数量，记第 $i$ 个盒子放的球的数量为 $a_i$，并且有 $\sum_{i=1}^ka_i=n$，那么
模仿上面的，把阶乘放在一起，弄出多重集合排列数。
\[g_n≟\sum_{k=1}^n\sum_{a}\binom n{a_1,a_2,\cdots,a_k}\prod_{i=1}^kf_{a_i}\]但！是！这！个！式！子！大！有！问！题！
试看下面两个问题有什么区别：
- $7$ 个不同的球分成 $3$ 堆，要求每堆数量分别为 $2,2,3$，求方案数。
- $7$ 个不同的球放到 $3$ 个不同的盒子里，要求每堆数量分别为 $2,2,3$，求方案数。
其中第二个问题我们已经解决过了。多重集合的排列数的第二种组合含义是有 $n$ 个不同的球要放入 $k$ 个不同的盒子里，其中第 $k$ 堆的球必须有 $a_i$ 个的方案数。所以第二个问题的答案是 $7!/(2!2!3!)=210$。
第一个问题的答案肯定不是 $210$，那是多少呢？我们不妨来数一数，先列出大小为 $3$ 的那一堆吧（数数能力也是组合数学的一种体现）：从小到大数，先数 $1$ 打头的，$123,124,125,126,127,134,135,136,137,145,146,147,156,157,167$，这总共有 $5+4+3+2+1=\binom62$ 种。$2$ 打头的有 $\binom52$ 种，$3$ 打头的有 $\binom42$ 种，$4$ 打头的有 $\binom32$ 种，$4$ 打头的有 $\binom22$ 种，所以大小为 $3$ 的那一堆有 $\binom62+\binom52+\binom42+\binom32+\binom22=35$ 种。如果我们选了 $123$，那么还剩下 $4567$ 要分成 $2$ 堆，从中选取 $2$ 个的方案数是 $\binom 42$ 吗？问题就出在这里。从 $4567$ 中选取 $2$ 个，选取 $45$ 和 $67$ 实际上是同一种方案，因为把 $45$ 拆出来，和把 $67$ 拆出来是一模一样的，因此，每个方案都被算了 $2$ 次，所以实际上是 $\binom42/2=3$ 种方案（$45+67,46+57,47+56$）。这样，总方案数就是 $35\times3=105$ 种。
脱离这个例子，我们知道了两者的问题是如果两堆有相同数量的球，那我们是无法区分这两堆的。
具体的说，如果令 $c_i$ 表示数量为 $i$ 的堆数，即
那么就应该将总方案数除以 $c_i!$。
更一般的，如果 $n$ 个不同的球分成 $k$ 堆，要求每堆的数量分别为 $a_1,a_2,\cdots,a_k$，那么方案数是
\[\binom n{a_1,a_2,\cdots,a_k}\prod_{i=1}^n\frac1{c_i!}\]所以我们修正一下上面的式子
\[g_n≟\sum_{k=1}^n\sum_{a}\binom n{a_1,a_2,\cdots,a_k}\prod_{i=1}^n\frac1{c_i!}\prod_{i=1}^kf_{a_i}\]可是还有一个问题。承接上面那个例子，当 $k=3$，分成 $2,2,3$ 三堆的时候，我们并不知道这个 $2,2,3$ 是怎么分配给三个指数生成函数的。也就是说，由于盒子是相同的，所以当指数生成函数的指数分别为 $2,2,3$ 或者 $2,3,2$ 或者 $3,2,2$ 的时候，其实是同一种方案。
我们只要知道，如果某种序列 $a_1,a_2,\cdots,a_k$ 的取值被算了 $t(a_1,a_2,\cdots,a_k)$，那在计数时，只有 $1/t(a_1,a_2,\cdots,a_k)$ 的贡献，这样就可以知道 $g_n$ 了。
我们不禁想起了多重集合的排列数的第一种组合含义：总共有 $n$ 个球，共有 $k$ 种颜色，其中第 $i$ 种颜色的球有 $a_i$ 个，相同颜色的球没有任何区别。将其排成一行的方案数即为多重集合的排列数。
现在我们有 $k$ 个指数生成函数，有若干种集合大小（相同的大小可以视为相同颜色）要分配给这 $k$ 个指数生成函数，其中第 $k$ 个集合大小的数量为 $c_i$，这是多重集合的排列数的第一种组合意义，因此
将其回代入 $g_n$ 可得
\[g_n=\sum_{k=1}^n\sum_{a}\binom n{a_1,a_2,\cdots,a_k}\frac1{\binom k{c_1,c_2,\cdots,c_n} }\prod_{i=1}^n\frac1{c_i!}\prod_{i=1}^kf_{a_i}\]如果我们把这两个多重集展开，约分，然后将阶乘绑定到生成函数上去
\[\frac{g_n}{n!}=\sum_{k=1}^n\frac1{k!}\prod_{i=1}^k\frac{f_{a_i} }{a_i!}\]将其写为多项式卷积
\[\hat G=\sum_{k=1}^\infty\frac1{k!}\prod\hat F^k=\exp\hat F\]不得不提的是，如果 $[x^0]\hat F(x)\ne0$，那就表示可以有空盒子。
可是我们的 $\hat G$ 表示的是若干个盒子，那我们岂不是可以取任意多个盒子，产生无限多种方案了吗？
为了避免这种情况，我们规定 $[x^0]\hat F(x)=0$ 必须成立，也就是说我们在进行多项式 $\exp$ 的组合含义时，盒子不能为空。
还记得上文的粉格子吗，其生成函数是 $\mathrm e^x-1$。
同理，$n$ 个不同的球放入一个盒子，并且盒子不能为空的指数生成函数也为 $\hat F(x)=\mathrm e^x-1$。
我们记 $n$ 个不同的球放入若干个相同盒子，并且每个盒子不能为空的指数生成函数为 $\hat G(x)$，根据 $\exp$ 的组合意义，我们知道 $\hat G(x)=\exp\hat F(x)=\exp(\mathrm e^x-1)$。
$n$ 个不同的球放入 $k$ 个相同盒子，并且每个盒子不能为空的方案数为第二类斯特林数 $n\brace k$，因此把 $n$ 个不同的球放入若干个相同盒子，并且每个盒子不能为空的方案数就是第二类斯特林数的行和，我们称其为贝尔数 $B_n$。
其从第一项开始为
\[1, 2, 5, 15, 52, 203, 877\]我们可以对 $\exp(\mathrm e^x-1)$ 泰勒展开来验证。
\[\begin{aligned} \exp(\mathrm e^x-1)&=1+x+x^2+\frac{5 x^3}{6}+\frac{5 x^4}{8}+\frac{13 x^5}{30}+\frac{203 x^6}{720}+\frac{877 x^7}{5040}+\mathcal O(x^8)\\ &=1+x+\frac{2}{2!}x^2+\frac{5}{3!}x^3+\frac{15}{4!}x^4+\frac{52}{5!}x^5+\frac{203}{6!}x^6+\frac{877}{7!}x^7+\mathcal O(x^8) \end{aligned}\]这也就是 LGP5748 集合划分计数。
$n$ 的圆排列数是把 $1,2,\cdots,n$ 排成一个环的方案数，其中旋转后的方案等价，但翻转不等价。
利用断环为链或者 pólya 引理，我们知道 $n$ 的圆排列数是 $(n-1)!$，我们同样可以用指数生成函数的知识去获得这个答案。
我们知道 $n$ 的全排列可以写成若干置换环。而圆排列有且仅有一个 $n$ 元置换环。
记 $\hat F(x)$ 表示 $n$ 个有标号点形成一个置换环的方案数的指数生成函数，也就是 $n$ 的圆排列的指数指数生成函数。
记 $\hat G(x)$ 表示 $n$ 个有标号点形成若干个置换环的方案数的指数生成函数，也就是 $n$ 的全排列的指数指数生成函数。
因为全排列是由若干个置换环组成的，所以 $\hat G(x)=\exp\hat F(x)$。
和之前那个例子不一样，之前我们已经知道了 $\hat F(x)$，而用多项式 $\exp$ 能求出 $\hat G(x)$。这里我们要求的是 $\hat F(x)$，也就是说如果我们能求出 $\hat G(x)$，那么 $\hat F(x)=\ln\hat G(x)$，是不是有点反演的意味在里面了。
$n$ 的全排列是 $n!$ 我们还是知道的，因此
这是一个指数生成函数，虽然看起来像也实际上的确是恒定数列 $1,1,1,\cdots$ 的普通生成函数，但是两者的意义不同。
所以
\[\hat F(x)=\ln\frac1{1-x}=-\ln(1-x)\]如果我们对 $\hat F$ 进行泰勒展开，马上就知道了 $[x^n]\hat F(x)=1/n=(n-1)!/n!$，也就是说 $n$ 的圆排列为 $(n-1)!$。
根据组合意义，我们还可以断定 $[x^0]\hat F(x)=0$。
求错排的指数生成函数。
从置换环的角度考虑，错排就是没有一元环的排列。
令 $\hat F(x)$ 表示 $n$ 个点不形成一元环的指数生成函数，显然 $[x^n]\hat F(x)=[n>1]/n!$。我们刚刚求出过圆排列的指数生成函数，将其减去 $x$ 即可。
令 $\hat G(x)$ 表示 $n$ 个点没有错排的指数生成函数。
LGP4841 [集训队作业2013]城市规划：求 $n$ 个有标号的点的简单无向连通图的方案数。
将点看作球，将一个联通块看成一个盒子。这里，一个盒子里放 $n$ 个有标号球的方案数不再是 $0$ 或者 $1$ 了。
记 $\hat F(x)$ 表示 $n$ 个有标号的点的简单无向连通图的方案数的指数生成函数，$\hat G(x)$ 表示 $n$ 个有标号的点的简单无向图的方案数的指数生成函数。因为简单无向图是由若干个简单无向连通图组成的，所以 $\hat G(x)=\exp\hat F(x)$。
$\hat G(x)$ 的条件很弱，任意的无向连通图都行，所以我们枚举任意两条边连或者不连即可
我们可以用 $\mathcal O(n)$ 的时间求出 $\hat G(x)$，再 $\mathcal O(n\log n)$ 的时间用多项式 $\ln$ 求出 $\hat F(x)$。
不动点：求有多少个置换 $f:[n]\to[n]$ 满足 $f^{k-1}=f^k$。
$nk\le2\times10^6,1\le k\le3$
不难发现 $f$ 是一个基环树森林。
任意一个点走 $k-1$ 步和走 $k$ 步到达的是同一个点，因此每个基环树的环都是自环，所以我们可以把自环基环树看成有根树。如果记根节点的深度为 $1$，那么这棵基环树的深度不超过 $k$。这样，问题就转化为 $n$ 个有标号点，深度不超过 $k$ 的有根树森林的计数。
记 $n$ 个点个有标号点，深度不超过 $k$ 的有根树的指数生成函数为
深度不超过 $k$ 的有根树，实际上就是深度不超过 $k-1$ 的若干棵有根树，把它们的根结点全部连到一个结点上去。因此
\[\hat F_k(x)=x\exp\hat F_{k-1}(x)\]这样就可以递推求解了。
我们知道 $n$ 个有标号点的无根树数量是 $\text{Prüfer}$ 序列，其指数生成函数为
\[\hat F(x)=\sum_{i=1}^\infty i^{i-2}\frac{x^i}{i!}\]那么 $n$ 个有标号点的无根树森林数量的指数生成函数就是 $\exp\hat F(x)$。
我们还知道 $n$ 个有标号点的有根树数量，其指数生成函数为
\[\hat F(x)=\sum_{i=1}^\infty i^{i-1}\frac{x^i}{i!}\]那么 $n$ 个有标号点的有根树森林数量的指数生成函数就是 $\exp\hat F(x)$。
根据刚刚的递推思路，把它们的根结点全部连到一个结点上去，我们可以写出 $\hat F$ 的另一个式子
\[\hat F(x)=x\exp\hat F(x)\]但是这个式子的 $F(x)$ 无初等表达，只能使用朗伯W函数（又名乘积对数函数，记为 $W(x)$，其中 $W_0$ 是 $x\mathrm e^x$ 在 $x\ge-1$ 时的反函数，$W_{-1}$ 是 $x\mathrm e^x$ 在 $x\le-1$ 时的反函数）给出 $\hat F(x)=-W_0(-x)$。
因此
令人震撼的是 mma 竟然会算这个无穷级数。