多项式EXP运算的组合意义
EGF一般用来处理多重集的排列问题，在其上可以定义多项式的exp运算，在处理一类问题的时候有独特的作用
我们考虑将n个有标号的元素分为k个非空无序集合的方案数，记其EGF为\(F_{k}\),再考虑\(f_i\)表示在这个我们定义的集合中对集合元素的计数方式（也就是考虑元素在集合内的排列方式的个数，这是一个只跟集合大小有关的值），那么根据生成函数的定义，我们不难得到下式
\(F_{k}(n)=\frac{n!}{k!}\sum_{\sum_{i=1}^{k}a_i=n}\prod_{j=1}^{k}\frac{f_{a_j}}{a_j!}\)，最后除以\(k!\)是因为这k个集合是无序的，而原本的多个多项式卷积显然是有序的
现在我们记\(\hat{F(x)}=\sum_{i=0}^{inf}f_i\frac{x^i}{i!}\),也就是原本的\(f_i\)的EGF
再记\(G_k(x)\)为\(F_k(n)\)的EGF，则有
\(G_k(x)=\sum_{n=0}^{inf}F_k(n)\frac{x^n}{n!}\)
\(=\sum_{n=0}^{inf}\frac{n!}{k!}(\sum_{\sum_{i=1}^{k}a_i=n}\prod_{j=1}^{k}\frac{f_{a_j}}{a_j!})\frac{x^n}{n!}\)
\(=\frac{1}{k!}\sum_{n=0}^{inf}(\sum_{\sum_{i=1}^{k}a_i=n}\prod_{j=1}^{k}\frac{f_{a_j}x^{a_j}}{a_j!})\)
\(=\frac{1}{k!}(\hat{F(x)})^k\)
如果我们考虑所有\(k\geq 0\),就有
\(\sum_{k\geq 0}G_k(x)=\sum_{k\geq 0}\frac{(\hat{F(x)})^k}{k!}=exp\hat{F(x)}\)
我们惊奇地发现，\(G(x)\)的指数生成函数居然就是\(f_x\)的生成函数的exp！
总结一下，多项式exp的组合意义就是：有标号元素构成的集合划分为任意个非空子集的总方案数。
来几个具体的例子
考虑大小为n的排列的个数是\(n!\),其指数生成函数是\(P(x)=\sum_{n\geq 0}\frac{n!x^n}{n!}=\sum_{n\geq 0}x^n=\frac{1}{1-x}\)
一个大小为n的圆排列个数是\((n-1)!\),其指数生成函数是\(G(x)=\sum_{n\geq 1}\frac{(n-1)!x^n}{n!}=\sum_{n\geq 1}\frac{x^n}{n}=-\ln(1-x)=ln(\frac{1}{1-x})\)
不难发现\(P(x)=expG(x)\)
仔细理解一下，众所周知，一个大小为n的排列一定可以拆成若干个环，每一个环内部的排列数就是一个圆排列的方案数，所以大小为n的排列的方案数就是把\(1,2...n\)分成若干个非空集合，每一个集合的圆排列方案数之积，这与我们上面讲到的exp的组合意义相符合
第二类斯特林数\(\{n,k\}\)的组合意义就是把n个数分成k个集合的方案数，这里一个集合的计数就是1，也就是说在上面推导过程中\(\hat{F(x)}=\{1,1,1....\}\)
其指数生成函数是\(G_{k}(x)=\sum_{n\geq 0}S(n,k)\frac{x^n}{n!}=\frac{1}{k!}(exp(x)-1)^k\)
贝尔数的组合意义是把n个数分成若干个非空集合的方案数，其生成函数是\(\hat{B}(x)=exp(e^x-1)\)
不难理解，贝尔数与第二类斯特林数的区别就在于对分成的非空集合的个数的限制，那么\(\hat{B(x)}=\sum_{k\geq0}G_k(x)\)也就是时分自然的，这也与上面的理论相符合
举一反三，我们考虑n个点带标号的生成树个数的EGF为\(\hat{F(x)}\),那么n个点带标号的森林的个数就是\(exp \hat{F(x)}\),意义就是将n个点分成若干个树的方案数
求n个点的有标号简单无向连通图的数量
这个可能并不是那么好直接想出来，但是按照我们刚刚的理论，可以考虑先求出n个点的有标号简单无向图的数量（不要要求连通），然后直接对其EGF直接取\(\ln\)就可以了
这个是非常好求的，就是一张完全图里面每一个点都有删或不删两种选择，其EGF就是\(\sum_{n\geq 0}2^{\binom{n}{2}}\frac{x^n}{n!}\)
所以答案就是\([x^n]\ln(\sum_{n\geq 0}2^{\binom{n}{2}}\frac{x^n}{n!})\)
对上文的拓展(环计数)
上文考虑的情况是将n个元素分成若干个无序集合的情况，如果集合之间是有序的，那么就要把对应的方案数乘回去
比如如果我们是要将所有集合排成一个环，那么n个集合之间的关系方案数就是\((n-1)!\)
所以老样子，还是考虑\(G_k(x)\)为将n个元素分成k个集合，集合之间组成一个k元环的方案数，集合内部计数方案的EGF为\(\hat{F(x)}\),则\(G_k(x)=\frac{(k-1)!}{k!}(\hat{F(x)})^k=\frac{1}{k}(\hat{F(x)})^k\)
\(\sum_{k\geq 1}G_k(x)=\sum_{k\geq 1}\frac{1}{k}(\hat{F(x)})^k=-\ln(1-\hat{F(x)})\)
求包含n个顶点，n条边的连通无向图的个数。顶点有标号，要求不存在重边和自环
首先不难发现图是一个基环树，图中存在一个大小\(\geq 3\)的环，并且环的每一个顶点都是一个有标号有根树的根。
那么此时思路就比较明显了，我们的目的就是把n个点分成\(\geq 3\)个集合，然后每一个大小为x的集合内部的计数就是大小为x的有标号有根树的计数，也就是\(x^{x-1}\)。其EGF就是\(T(x)=\sum_{n\geq 1}\frac{n^{n-1}x^n}{n!}\)
所以\(G_k(x)=\frac{1}{k}T(x)^k\)
那么答案就是\(\frac{1}{2}\sum_{k\geq 3}G_k(x)=-\frac{1}{2}\ln(1-T(x))-\frac{T(x)}{2}-\frac{T(x)^2}{4}\)
最后乘上\(\frac{1}{2}\)是因为这里的环是没有方向的，可以翻转