指数生成函数

指数生成函数(Exponential generating function,EGF)定义为

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

因此序列的指数生成函数的积得到的是的指数生成函数。这在一些有标号的计数中会很有用。

常用封闭形式

首先有的泰勒展开式:

那么简单拓展为

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

置换环与圆排列

考虑 n 个元素的排列数的指数生成函数:

另一方面,个元素的圆排列排列数的指数生成函数:

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

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

拓展

错排数的生成函数?

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

城市规划

题意:求出有个点的有标号简单连通无向图的个数。

算法一

表示个点简单无向连通图的个数,表示个点的图的个数。那么

化简得到

我们定义三个生成函数

那么显然可以得到,那么,多项式求逆即可。

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

算法二

表示个点的简单无向图的个数,表示个点简单无向连通图的个数。对应的指数生成函数为

其中

我们尝试用表示。考虑表示的含义。它表示个点分成个连通块的“排列数”。因为在分的过程中我们是钦定了连通块之间的顺序(这是 EGF 乘法运算的组合意义)。因此还需要除以才能得到个点分成个连通块的图的个数。因此得到

因此,那么

TJOI2015 概率论

表示个结点的二叉树总数,表示个结点的二叉树的叶子结点数的和。

容易发现是卡特兰数。类似地可以得到

其中。类似地,设,那么得到

代入解得

用牛顿二项式展开得到

那么带回原式得到

根据卡特兰数的生成函数

对应项相除可以得到

答案即所求。

POJ3734 Blocks

容易得到生成函数为

那么展开得到

51nod1728 不动点

题意:求有多少个映射,使得。(这个大圈表示复合)

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

表示答案的指数生成函数。显然

表示个点深度不超过的有根树的方案数。是指数生成函数。显然。考虑的递推式,可以得到。整理一下得到

于是得到

注意这题卡常,可以根据合理设置长度来卡常。

CF891 E

减少的值是,那么题目相当于要求

对于后者,乘上一个转化为计数问题:

构造生成函数,对于可以构造,那么就可以构造一个 OGF:

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

我们直接求出的系数,记为。那么可以得到

期望为

答案为

小朋友与二叉树

考虑。设答案的 OGF 为。那么可以列出方程

解得

,由于分母常数项不能为 0,因此舍掉负根,得到

多项式求逆、幂函数即可()。

分拆数

分拆数(拆分数,划分数)的生成函数为

算法一

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

两边同时得到

那么我们预处理,再回去即可。时间复杂度。但常数较大。

算法二

首先介绍一下五边形数:

对于广义五边形数。容易证明,

接下来介绍欧拉函数(复变函数),其定义为

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

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

于是直接求即可。求的复杂度是的,多项式求逆复杂度。总复杂度