指数生成函数学习笔记

指数生成函数

指数生成函数（Exponential generating function，EGF）定义为

$$\hat{F}(x)=\sum_{i\ge 0}a_i\frac{x^i}{i!}$$

指数生成函数的运算不是简单的卷积：

$$\begin{aligned} \hat{F}(x)\hat{G}(x)&=\sum_{i\ge 0}\sum_{j\ge 0}a_ib_j\frac{x^{i+j}}{i!j!}\\ &=\sum_{k\ge 0}\sum_{i=0}^ka_ib_{k-i}\frac{x^k}{i!(k-i)!}\\ &=\sum_{k\ge 0}\sum_{i=0}^k\binom{k}{i}a_ib_{k-i}\frac{x^k}{k!} \end{aligned}$$

因此序列$a_i$和$b_i$的指数生成函数的积得到的是$\sum_{j=0}^i\dbinom{i}{j} a_ib_{i-j}$的指数生成函数。这在一些有标号的计数中会很有用。

常用封闭形式

首先有$e^x$的泰勒展开式：

$$\hat{G}(x)=\sum_{i\ge 0}\frac{x^i}{i!}=e^x$$

那么简单拓展为$e^{-x}$：

$$\hat{G}(x)=\sum_{i\ge 0}\frac{(-x)^i}{i!}=\sum_{i\ge 0}(-1)^i\frac{x^i}{i!}$$

这两个可以拓展出奇数和偶数阶乘的封闭形式。

置换环与圆排列

考虑 n 个元素的排列数$p_n=n!$的指数生成函数：

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

另一方面，$n$个元素的圆排列排列数$q_n=(n-1)!$的指数生成函数：

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

这两者有什么联系？容易发现，（置换）排列可以理解为是若干个环（置换环）的集合。而这些环之间的顺序我们不考虑。因此$\exp\hat{Q}$可以理解为是若干个带标号的圆排列组合在一起的方案数的指数生成函数，即$\hat{P}$。反之，$\ln\hat{P}$则相当于把构成方案分成若干个具有相同性质的部分，这些部分的生成函数。

另一方面，这也解释了$\exp$和$\ln$的组合意义，这在求一些生成函数的时候会非常有用。

拓展

错排数的生成函数？

直接用容斥的式子似乎不太好做。考虑其组合意义就是置换环大小大于 1 的置换数量。那么我们把圆排列数的$x$这一项去掉，然后$\exp$回去即可：

$$\hat{F}(x)=\exp(\hat{Q}(x)-x)=\exp\left(\ln\left(\frac{1}{1-x}\right)-x\right)=\frac{e^{-x}}{1-x}$$

有标号简单连通无向图计数

题目链接：城市规划。

求出有$n(n\le 130000)$个点的有标号简单连通无向图的个数。

算法一

设$f(n)$表示$n$个点简单无向连通图的个数，$g(n)$表示$n$个点的图的个数。那么

$$g(n)=2^{\binom{n}{2}}$$

且

$$g(n)=\sum_{i=1}^n\binom{n-1}{i-1}f(i)g(n-i)$$

化简得到

$$\frac{g(n)}{(n-1)!}=\sum_{i=1}^n\frac{f(i)}{(i-1)!}\frac{g(n-i)}{(n-i)!}$$

我们定义三个生成函数

$$\begin{aligned} F(x)&=\sum_{i\ge 1}\frac{f(i)}{(i-1)!}x^i\\ G(x)&=\sum_{i\ge 0}\frac{g(i)}{i!}x^i\\ H(x)&=\sum_{i\ge 1}\frac{g(i)}{(i-1)!}x^i \end{aligned}$$

那么显然可以得到$H=FG\pmod{x^{n+1}}$，那么$F=HG^{-1}\pmod{x^{n+1}}$，多项式求逆即可。

最后算完了别忘了把阶乘乘回去。

算法二

设$g(i)$表示$i$个点的简单无向图的个数，$f(i)$表示$i$个点简单无向连通图的个数。对应的指数生成函数为

$$\hat{G}(x)=\sum_{i\ge 0}g(i)\frac{x^i}{i!}\\ \hat{F}(x)=\sum_{i\ge 0}f(i)\frac{x^i}{i!}$$

其中

$$g(i)=2^{\binom{i}{2}}$$

我们尝试用$\hat{F}$表示$\hat{G}$。考虑$[x^n]\hat{F}^i(x)$表示的含义。它表示$n$个点分成$i$个连通块的“排列数”。因为在分的过程中我们是钦定了连通块之间的顺序（这是 EGF 乘法运算的组合意义）。因此还需要除以$i!$才能得到$n$个点分成$i$个连通块的图的个数。因此得到

$$\hat{G}(x)=\sum_{i\ge 0}\frac{\hat{F}^i(x)}{i!}$$

因此$\hat{G}(x)=\exp \hat{F}(x)$，那么$\hat{F}(x)=\ln \hat{G}(x)$。

有标号二分图计数

首先考虑二分染色图计数。所谓二分染色图指区分左右部的二分图。这个比较简单：

$$f_n = \sum_{i = 0} ^ n \binom{n}{i} 2^{(n - i) i}$$

设其对应的 EGF 为$F(x)$。根据$ab = \binom{a + b}{2} - \binom{a}{2} - \binom{b}{2}$，我们可以很容易将$F$表示为卷积的形式。

然后我们考虑将二分染色图个数转化为二分图个数。若连通块个数为$k$的二分染色图为$t$，那么连通块个数为$k$的二分图个数为$\frac{t}{2^k}$。这启发我们利用连通二分图的个数建立关系。

假设二分图个数的 EGF 为$G(x)$，则连通二分图的个数的 EGF 显然为$\ln G(x)$。于是连通的二分染色图个数为$2\ln G(x)$，于是

$$2\ln G = \ln F$$

因此$G = \sqrt{F}$。使用多项式开根即可。

TJOI2015 概率论

设$h(i)$表示$i$个结点的二叉树总数，$f(i)$表示$i$个结点的二叉树的叶子结点数的和。

容易发现$h(i)=\sum_{j=0}^{i-1}h(j)h(i-j-1)$是卡特兰数。类似地可以得到

$$f(i)=2\sum_{j=1}^{i-1}f(j)h(i-j-1) \quad (i\ge 2)$$

其中$f(0)=0,f(1)=1$。类似地，设$F(x)=\sum_{i\ge 0}f(i)x^i$，那么得到

$$\begin{aligned} F(x)&=\sum_{i\ge 0}f(i)x^i\\ &=x+2\sum_{i\ge 2}\sum_{j=1}^{i-1}f(j)h(i-j-1)x^jx^{i-j-1}x\\ &=x+2x\sum_{j\ge 1}f(j)x^j\sum_{i\ge 0}h(i)x^{i}\\ &=x+2xF(x)C(x) \end{aligned}$$

代入$C(x)=\dfrac{1-\sqrt{1-4x}}{2x}$解得

$$F(x)=\frac{x}{\sqrt{1-4x}}$$

用牛顿二项式展开得到

$$(1-4x)^{-\frac{1}{2}}=\sum_{i\ge 0}\binom{-\frac{1}{2}}{i}(-4x)^i\\ =\sum_{i\ge 0}\frac{(-1)^i(2i)!}{4^ii!i!}(-4x)^i\\ =\sum_{i\ge 0}\binom{2i}{i}x^i\\$$

那么带回原式得到

$$F(x)=\sum_{i\ge 1}\binom{2i-2}{i-1}x^{i}$$

根据卡特兰数的生成函数

$$C(x)=\sum_{i\ge 0}\frac{1}{i+1}\binom{2i}{i}x^i$$

对应项相除可以得到

$$\frac{[x^n]F(x)}{[x^n]C(x)}=\frac{\binom{2n-2}{n-1}}{\frac{1}{n+1}\binom{2n}{n}}=\frac{n(n+1)}{2(2n-1)}$$

答案即所求。

POJ3734 Blocks

容易得到生成函数为

$$e^{2x}\left(\frac{e^x+e^{-x}}{2}\right)^2\\ =\frac{e^{4x}+2e^{2x}+1}{4}$$

那么展开得到

$$\hat{G}(x)=1+\sum_{i\ge 1}(4^{i-1}+2^{i-1})\frac{x^i}{i!}$$

51nod1728 不动点

题意：求有多少个映射$f:\{1,2,\cdots,n\}\to \{1,2,\cdots,n\}$，使得$\bigcirc_{i=1}^k f=\bigcirc_{i=1}^{k-1}f$。（这个大圈表示复合）

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

可以发现，我们要求的是$n$个点带标号的深度不超过$k$的有根树森林计数。

设$\hat{F}_k(x)$表示答案的指数生成函数。显然$\hat{F}_1(x)=e^x$。

设$[x^n]\hat{G}_k(x)$表示$n$个点深度不超过$k$的有根树的方案数。$\hat{G}_k(x)$是指数生成函数。显然$\hat{G}_1(x)=x$。考虑$\hat{G}_k(x)$的递推式，可以得到$[x^n]\hat{G}_k(x)=n[x^{n-1}]\hat{F}_{k-1}(x)$。整理一下得到$\hat{G}_k(x)=x\hat{F}_{k-1}(x)$。

于是得到$\hat{F}_k(x)=\exp \hat{G}_k(x)=\exp(x\hat{F}_{k-1}(x))$。

注意这题卡常，可以根据$nk\le 2\times 10^6$合理设置长度来卡常。

CF891 E

设$a_i$减少的值是$b_i$，那么题目相当于要求$E(\prod a_i-\prod(a_i-b_i))=\prod a_i-E(\prod(a_i-b_i))$。

对于后者，乘上一个$n^k$转化为计数问题：

$$E=\frac{1}{n^k}\sum_{\sum b_i=k}\frac{k!}{\prod b_i!}\prod_{i=1}^n(a_i-b_i)\\ =\frac{k!}{n^k}\sum_{\sum b_i=k}\prod_{i=1}^n\frac{a_i-b_i}{b_i!}$$

构造生成函数，对于$\dfrac{a_i-b_i}{b_i!}$可以构造$\sum_{j\ge 0}\dfrac{a_i-j}{j!}$，那么就可以构造一个 OGF：

$$F(x)=\prod_{i=1}^n\sum_{j\ge 0}\frac{a_i-j}{j!}x^j$$

虽然这是一个 OGF，但是我们是可以把它当 EGF 来用的。因此做一下化简：

$$\begin{aligned} F(x)&=\prod_{i=1}^n\sum_{j\ge 0}\frac{a_i-j}{j!}x^j\\ &=\prod_{i=1}^n(a_ie^x-xe^x)\\ &=e^{nx}\prod_{i=1}^n(a_i-x)\\ \end{aligned}$$

我们直接$O(n^2)$求出$G(x)=\prod_{i=1}^n(a_i-x)$的系数，记为$c_i$。那么可以得到

$$\begin{aligned} F(x)&=e^{nx}G(x)\\ &=\sum_{i\ge 0}\frac{(nx)^i}{i!}\sum_{j\ge 0}c_jx^j\\ &=\sum_{i\ge 0}\frac{n^ix^i}{i!}\sum_{j\ge 0}c_jx^j\\ &=\sum_{k\ge 0}x^k\sum_{i=0}^k\frac{n^i}{i!}c_{k-i} \end{aligned}$$

期望为

$$\frac{k!}{n^k}[x^k]F(x)=\sum_{i=0}^k\frac{k^{\underline{i}}}{n^{i}}c_i=\sum_{i=0}^{\min(n,k)}\frac{k^{\underline{i}}}{n^{i}}c_i$$

答案为

$$\prod_{i=1}^na_i-\sum_{i=0}^{\min(n,k)}\frac{k^{\underline{i}}}{n^{i}}c_i$$

小朋友与二叉树

考虑$G(x)=\sum_{i=1}^nx^{c_i}$。设答案的 OGF 为$F(x)$。那么可以列出方程

$$F=F^2G+1$$

解得

$$F=\frac{1\pm \sqrt{1-4G}}{2G}=\frac{2}{1\mp \sqrt{1-4G}}$$

取$x=0$，由于分母常数项不能为 0，因此舍掉负根，得到

$$F(x)=\frac{2}{1+\sqrt{1-4G(x)}}$$

多项式求逆、幂函数即可（$[x^0]F(x)=1$）。

分拆数

分拆数（拆分数，划分数）的生成函数为

$$P(x)=\prod_{i\ge 1}\left(\sum_{j\ge 0}x^{ij}\right)$$

算法一

利用所学知识，我们来化简一下该生成函数：

$$P(x)=\prod_{i\ge 1}\frac{1}{1-x^i}$$

两边同时$\ln$得到

$$\begin{aligned} \ln P(x)&=\ln\prod_{i\ge 1}\frac{1}{1-x^i}\\ &=\sum_{i\ge 1}\ln\frac{1}{1-x^i}\\ &=-\sum_{i\ge 1}\ln(1-x^i)\\ &=\sum_{i\ge 1}\sum_{j\ge 1}\frac{x^{ij}}{j}\\ &=\sum_{i\ge 1}x^i\sum_{j|i}\frac{1}{j}\\ \end{aligned}$$

那么我们$O(n\log n)$预处理$\ln P(x)$，再$\exp$回去即可。时间复杂度$O(n\log n)$。但常数较大。

算法二

首先介绍一下五边形数：$p_n=\dfrac{1}{2}n(3n-1),n\in\mathbf{N}$。

对于广义五边形数，$n\in\mathbf{Z}$。容易证明，$p_n\ge 0(n\in \mathbf{Z})$。

接下来介绍欧拉函数（复变函数），其定义为

$$\phi(x)=\prod_{i\ge 1}(1-x^i)$$

与之相关的是五边形定理，它描述了五边形数与欧拉函数的关系：

$$\phi(x)=\sum_{n=-\infty}^\infty(-1)^nx^{p_n}$$

另外还有一个性质，欧拉函数的倒数是分拆数的生成函数：

$$\phi^{-1}(x)=\sum_{n\ge 0}P(n)x^n$$

于是直接求即可。求$\phi(x)\bmod {x^n}$的复杂度是$O(\sqrt{n})$的，多项式求逆复杂度$O(n\log_2n)$。总复杂度$O(n\log_2n)$。