【EGF】

对于一个数列 \(<f_n>\)，定义其指数型生成函数（EGF）\(\hat{F}(x)=\displaystyle\sum_{n\ge 0}\dfrac{f_n}{n!}x^n\)。实际上 \(EGF<f_n>=OGF<\dfrac{f_n}{n!}>\)

定理：若 \(<a_n>\) 的 EGF 为 \(\hat{A}(x)\)，\(<b_n>\) 的 EGF 为 \(\hat{B}(x)\)，\(<c_n>\) 的 EGF 为 \(\hat{C}(x)\)，则 \(c_n=\displaystyle\sum_{i+j=n}(^n_i)a_ib_j\)。即 \(c\) 是 \(a,b\) 的二项式卷积结果。

【EGF 有什么用？】

比如我们要算一个数列的第 \(n\) 项，就可以用一些多项式手法求出它的 EGF。这里说的求出 EGF 是求出 EGF 的前 \(n\) 项系数。

而 EGF 的第 \(n\) 项系数是 \(\dfrac{a_n}{n!}\)，算出了这个，显然也能算出 \(a_n\)。

【应用：组合计数对象的拼接】

树+圈 计数

1. 有标号 \(n\) 个点恰好组成一棵树的方案数 \(t_n=n^{n-2}\)。（Cayley 公式）

2. 有标号 \(n\) 个点恰好组成一个圈（禁止重边自环）的方案数 \(c_n=\begin{cases}(n-1)!/2&n>2\\0&n\le 2\end{cases}\)

组合问题：\(n\) 个点恰好组成一棵树和一个圈的方案数 \(a_n\) 是多少？

\(a_n=\sum_{i=0}^nC_{n}^it_ic_{n-i}\)，即从 \(n\) 个点里选若干个点组成树，其余的组成圈。

发现 \(a_n\) 就是 \(t_n,c_n\) 的二项式卷积，所以 \(a_n\) 的 EGF 等于 \(t_n,c_n\) 的 EGF 乘积。

有标号固定连通块数量无向图计数

\(x\) 个点有标号无向图的数量 \(f(x)=2^{C^2_x}\)，即每条可能的边选或不选。

那么 \(x\) 个点有标号无向连通图的数量 \(g(x)\)？

考虑有两个连通块的数量：\(g_2(x)=\displaystyle\dfrac{1}{2!}\sum_{i=1}^{n-1}(^n_i)f(i)\cdot f(n-i)\) 即枚举一个连通块的点，分别计算再相乘。有一个 \(\dfrac{1}{2!}\) 的原因是树之间会重复计算。所以 \(\hat{g_2}(x)=\dfrac{1}{2}\hat{f}(x)\hat{f}(x)\)。

更进一步，\(\hat{g_k}(x)=\dfrac{1}{k!}(\hat{f}(x))^k\)。

所以 \(x\) 个点有标号的有若干个连通块的图的数量 \(h(x)\) 满足：\(\hat{h}(n)=\exp(\hat{f}(x))\)。

其实不一定是连通图有这个规律！

比如 \(x\) 个点形成一个圈的 EGF: \(\hat{f}(x)\)，和形成若干个圈的 EGF: \(\hat{g}(x)\) 满足 \(\hat{g}(x)=\exp(\hat{f}(x))\)。

所以形成一个满足条件 P 的图的 EGF，和形成若干个满足条件 P 的图的 EGF，只差一个 \(\exp\)。

这是巧合吗？我们看下一个例子。

排列数与圆排列

排列数 \(p_i=i!\) 的 EGF：\(\hat{p}(x)=\displaystyle\sum_{n\ge 0}\dfrac{p_n}{n!}x^n=\sum_{n\ge 0}x^n=\dfrac{1}{1-x}\)。（最后一步错位相减）

圆排列 \(q_i=(i-1)!\) 的 EGF：\(\hat{q}(x)=\displaystyle\sum_{n\ge 1}\dfrac{(n-1)!}{n!}x^n=\sum_{n\ge 1}\dfrac{x^n}{n}=\ln \dfrac{1}{1-x}\)。

（因为 \(\displaystyle\sum_{n\ge 1}\dfrac{x^n}{n}\) 的导 \(=\sum x^{n-1}\)）

我们发现 \(\hat{p}(x)=\exp(\hat{q}(x))\)！

为什么呢？如果把排列看作一个置换，则 "排列" 就是若干个 "圆排列" 组成的。而我们也验证了一个重要的性质：

如果一个东西 \(p\) 是由若干个另一个东西 \(q\) 组成，则 \(\hat{p}(x)=\exp(\hat{q}(x))\)，和上面的结论相同。

\(\exp(f(x))=\displaystyle\sum_{i\ge 0}\dfrac{f(x)^i}{i!}\)，这是一个复合函数。

错排问题

考虑一个问题 Q：让 \(1\sim n\) 每个数指向另一个数，不允许指向自己，使得最终形成一个环的方案数。

\(q_n=(n-1)!,q_1=q_0=0\)。

则 \(\hat{Q}(x)=\displaystyle\sum_{n=2}^{+\infty}\dfrac{q_n}{n!}\cdot x^n=\sum_{n=2}^{+\infty}\dfrac{x^n}{n}=\ln(\dfrac{1}{1-x})-x\)。

所以错排的 EGF 就是 \(\exp(\hat{Q}(x))\)。进而可以求出错排的答案。

连通图计数

因为无向图（有若干个连通块）的方案数 \(f_n=2^{C_n^2}\)，所以一个连通块的 EGF = \(\ln(\hat{f}(x))\)。

BZOJ4228

题意：求 \(n\) 个点的无向图数量，满足不存在三个相互可达的点 \(a,b,c\)，使得 \(dis(a,b),dis(b,c),dis(a,c)\) 不全相同。

首先发现不可能有长度为 \(3\) 的倍数的环，其次发现不会有点的度数 \(\ge 3\)。

由此推出图的结构为若干个链 + 若干个长度非 \(3\) 的倍数的环。

考虑 \(n\) 个点一条链的 EGF：\(\hat{A}(x)=x+\displaystyle\sum_{i=2}^n\dfrac{i!/2}{i!}x^i\)。

然后考虑 \(n\) 个点长度非 \(3\) 的倍数的环的 EGF: \(\hat{B}(x)=\displaystyle\sum_{i>3,3\not\mid i}\dfrac{(i-1)!}{2}\cdot\dfrac{x^i}{i!}=\sum_{i>3,3\not\mid i}\dfrac{x^i}{2i}\)。

然后考虑 \(n\) 个点是链或者长度非 \(3\) 倍数环的 EGF: \(\hat{C}(x)=\hat{A}(x)+\hat{B}(x)\)。

原问题是若干个链或者非 \(3\) 倍数环，所以原问题的 EGF 是 \(\exp(\hat{C}(x))\)。

基环树计数

\(n\) 个点基环树的个数？

\(n\) 个点有根树的个数：\(r_n=n^{n-2}\times n=n^{n-1}\)，因为要从生成树决定一个根。

\(r_n\) 的生成函数 \(\hat{R}(x)=\sum \dfrac{r_n}{n!}x^n\)。

枚举基环树的环上有 \(k\) 个点。考虑枚举拆开环后每一颗树的结点个数。

个数 \(b_n^{(k)}=\displaystyle\sum_{i_1+\dots+i_k=n}\dfrac{1}{2k}(^{\;\;\;n}_{i_1,i_2,\dots,i_k})r_{i_1}\cdot r_{i_2}\cdots r_{i_k}\)

（为什么是 \(\dfrac{1}{k}\) 不是 \(\dfrac{1}{k!}\)？因为环有顺序，不会重复 \(k!\) 次）

目标就是求 \(\displaystyle\sum_{k=3}^{+\infty}b_n^{(k)}\)。

设 \(b_n^{(k)}\) 以 \(n\) 为变量的 EGF 是 \(\hat{B}^{(k)}(x)\)。

如何求 \(\hat{B}^{(k)}(x)\)？考虑另一个函数 \(\hat{C}^{(k)}(x)=\hat{B}^{(k)}(x)\times 2k\)。设这个 EGF 对应的原函数是 \(c_n^{(k)}\)。

观察到 \(\displaystyle\sum_{i_1+\dots+i_k=n}\dfrac{r_{i_1}}{i_1!}\cdot \dfrac{r_{i_2}}{i_2!}\cdots \dfrac{r_{i_k}}{i_k!}=\dfrac{c_n^{(k)}}{n!}\)。

所以 \(\hat{R}(x)^k=\hat{C}(x)\)。

所以 \(\hat{B}^{(k)}(x)=\dfrac{1}{2k}(\hat{R}(x))^k\)

所以 \(\displaystyle\sum_{k=3}^{+\infty}b_n^{(k)}=\dfrac{1}{2}\sum_{k=3}\dfrac{1}{k}\hat{R}(x)^k=\dfrac{1}{2}[\sum_{k=1}\dfrac{1}{k}\hat{R}(x)^k-\hat{R}(x)-\dfrac{\hat{R}(x)}{2}]=\dfrac{1}{2}[-\ln(1-\hat{R}(x))-\hat{R}(x)-\dfrac{\hat{R}(x)}{2}]\)。

【多重集排列计数型】

有限多重集

\(S\) 是一个多重集，共 \(k\) 种数，每种有 \(n_i\) 个。问从中选 \(n\) 个排列的个数 \(t_n\)。

有 \(\hat{T}(x)=\displaystyle\prod_{i=1}^k\hat{G_i}(x)\)。其中 \(\hat{G_i}(x)\) 表示 \(<1,1,1,\dots,1>\)（共 \(n_i+1\) 个 \(1\)） 的 EGF。