浅谈 Exp 的组合意义

· · 算法·理论

我们平时在使用组合数学时，常常都是从实际问题出发。但如果换一个角度，将问题抽象化，去研究这类抽象的组合问题，我们能有怎样的收获？

前置知识：生成函数（小广告：生成函数杂谈：从卡特兰数开始）。

小声提一下：\text{Exp} 是指数的英文 \mathsf{exponent} 的缩写，一般指底数是 e 的指数。

对于一个大小为 i 的集合，我们记它的方案数为 f_i，保证 f_0=0。

注意：这里的方案数 f_i 可以有任何意义，比如说 f_i 是有 i 个节点的二叉树的形态数。只不过我们要研究的是抽象的问题，所以不会对 f_i 的具体意义加以声明。不过为了方便理解，我会用一些形象的比喻。

就像上面关于 f_i 的定义，我们同样可以有形象的比喻：

假设一个袋子里有 i 个小球（小球间互不相同），这 i 个小球会处于“量子态”中，从宏观上看有 f_i 种不同的状态（即方案数）。如果袋子里一个小球也没有，那就是 0 种状态（即 f_0=0）。

记数列 \{f_i\} 的 \text{EGF} 为 F(x)，注意是指数型生成函数哦。

现有 n 个不同的小球（分别标号 1\sim n），我想把这些小球分到若干个相同的袋子中（即袋子间无序）。

对于任意一种分法，都会有若干的袋子，并且每个袋子中的小球都会有自己的状态数。这时候，我们就称这种分法的状态数为每个袋子的状态数的积。比如我把 6 个球分成 \{1,2,3\} 一组，\{4,5\} 一组，\{6\} 一组，那么这种分法的状态数就是 f_1\times f_2\times f_3。

记所有分法的状态数和为 g_n。例如 n=2 时可以有以下分法：

\{1\}+\{2\},\{1,2\}

（不同的分法间用逗号隔开，同种分法的各个袋子间用加号相连）故 g_2=f_1\times f_1+f_2。现在，我们想知道的是：数列 \{g_i\} 与 \{f_i\} 之间的关系。推式子时间到了！

考虑枚举 1 号球所在袋子内球的数量：

g_n=\sum_{i=1}^{n}C_{n-1}^{i-1}\times f_i\times g_{n-i}

解释一下这条式子：式子里的组合数相当于 1 号球所在袋子内其他球的可能组成方案（在 2\sim n 的小球中随机选 i-1 个幸运小球和 1 放进同个袋子中，有 C_{n-1}^{i-1} 种方案）。那么对于 1 号球所在袋子，本身有 f_i 种状态；而对于剩下的 n-i 个小球，根据数列 \{g_i\} 的定义，可将它们的状态数视为 g_{n-i}。

稍稍整理一下，因为 f_0=0，所以可以直接把 i=0 纳进去（定义 \frac {f_0}{(-1)!}=0）：

\frac {g_n}{(n-1)!}=\sum_{i=0}^{n}\frac{f_i}{(i-1)!}\times \frac {g_{n-i}}{(n-i)!} \qquad\text{ (1) }

快用生成函数碾过去。别着急，先记 \{g_i\} 的 \text{EGF} 为 G(x)，然后我们有一些小结论：

F'(x)=\sum_{i=1}^{+\infty}\frac {f_i}{(i-1)!}x^{i-1}

很好证，直接对 \text{EGF} 定义式求导就好了。G'(x) 的结论类似。

那么 (1) 式用生成函数的形式表达就是：

G'(x)=F'(x)* G(x)

最关键的步骤来了：把 G(x) 除过去后两边积分！（不考虑常数）

\begin{aligned} \int \dfrac {G'(x)}{G(x)}&=\int F(x)\\ \ln(G(x))&=F(x)\\ G(x)&=e^{F(x)} \end{aligned}

到这里可谓是酣畅淋漓，我们不仅解决了 \{g_i\} 与 \{f_i\} 关系的问题，更是找到了 \text{Exp} 的组合意义！

让我们重新组织一下 \text{Exp} 的组合意义：

将 n 个互异元素分到若干非空的无序集合中，大小为 i 的集合内有 f_i 种方案，记最后的总方案数为 g_n。则两者的 \text{EGF} 满足 G(x)=e^{F(x)}。

我们可以把 \text{Exp} 的组合意义看作是一种模型，在题目满足「元素互异」、「集合非空且无序」时就可以使用。例如这一道：P5748 集合划分计数，题意如下：

有 n 个互异元素，将它们分到若干个非空的无序集合中，求方案数。

先记答案为 g_n，例如 g_2=2,g_3=5。观察到题面满足「元素互异」、「集合非空且无序」的条件，说明此题可用 \text{Exp} 的组合意义解决。想要求 g_n，我们只需知道数列 \{f_i\} 长啥样。

显然对于每个集合，无论有几个元素，内部都只有 1 种方案，即 f_i=1。但要注意的是 f_0=0，因为集合非空，空集合不能作为方案。不难发现，\{f_i\} 的 \text{EGF} 是 e^x-1。

故我们可以得到：\{g_i\} 的 \text{EGF} 为 e^{F(x)}=e^{e^x-1}，此题结束，拿个多项式 \text{Exp} 的板子搞一下就好了。

再来一道题目：P4841 [集训队作业2013]城市规划。题意简述：

求有 n 个点的简单（无重边无自环）有标号无向连通图数量。

记答案为 h_n，例如 h_2=1,h_3=4。那么要怎样把 \text{Exp} 的组合意义和这道题联系在一起呢？

首先，我们知道，在不考虑连通图的限制下，n 个点的有标号无向简单图有 2^{\binom{n}{2}} 个。因为 n 个点之间有 \binom n 2 条边，这些边各自有存在或不存在两种状态，所以这些图总共就有 2^{\binom n 2} 种方案。

接下来，我们考虑连通图这一条件。不难发现，每个图都是由若干个连通块凑在一起得来的。换句话说，每个图都是通过「将 n 个点划分到若干个连通块」得来的。

欸？这好像和 \text{Exp} 的组合意义有点类似。如果把「点」视为元素，「连通块」视为集合的话，那么 \text{Exp} 的组合意义翻译到这道题里面就是：把 n 个有标号的点分到若干个无序的连通块中总共有 2^{\binom n 2} 种方案。

并且根据定义，对于一个有 n 个点的连通块，其内部的方案数是 h_n。若记 \{h_i\} 的 \text{EGF} 为 H(x)，记 \{2^{\binom i 2}\} 的 \text{EGF} 为 F(x)。那么根据 \text{Exp} 组合意义，它们就应该满足：

F(x)=e^{H(x)}

等价于：H(x)=\ln F(x)，那么我们只需求出 F(x)，再用多项式 \ln 搞一下就好了。

此外，\text{Exp} 组合意义还可用于推导有标号无根树的数量。

众所周知，根据 Prufer 序列的知识，n 个点的有标号无根树有 n^{n-2} 种。那要怎样推导？

设有标号有根树的数量是 f_n，\{f_i\} 的 \text{EGF} 为 F(x)。为什么要设成有根树？因为方便研究。

现在，假设我们面对着一棵有根的树。接下来，我们把这个根拿掉，这棵树就会变成由若干棵有根树组成的集合（规定子树的根与原树的根相邻）。

不难发现，剩下的 (n-1) 个点被分在若干个子树中。这又与 \text{Exp} 的组合意义类似，那么根据其结论，这 (n-1) 个点的分法数的 \text{EGF} 就是 e^{F(x)}。

那么有 xe^{F(x)}=F(x)，乘上 x 是为了补回被拿走的根。

再根据拉格朗日反演（拉格朗日反演）的知识，就可以得到 f_n=n^{n-1}。因为要求的是无根树，所以要除个 n，答案就是 n^{n-2}。

讲这个主要是作为 \text{Euler} 变换的引入，不过单看 \text{Exp} 的组合意义，其实还是挺妙的。