生成函数

普通生成函数

等比数列

数列的生产成函数的封闭式为

生成函数

,(是常数)

斐波那其数列

通过求解

得

指数生产成函数(exponential generating function，EGF)

运算

因此 是序列 的指数生成函数。

圆排列

圆排列与排列的关系

生成树计数

如果 个点 带标号 生成树的 EGF 是 ，那么 个点 带标号 生成森林的 EGF 就是 ——直观理解为，将 个点分成若干个集合，每个集合构成一个生成树的方案数之积。

图

如果 个点带标号无向连通图的 EGF 是 ，那么 个点带标号无向图的 EGF 就是 ，后者可以很容易计算得到 。因此要计算前者，只需要一次多项式 即可。

错排数:长度为 的一个错排是满足 的排列。

不动点：

有多少个映射 ，使得

。

考虑 向 连边。相当于我们从任意一个 走 步和走 步到达的是同一个点。也就是说基环树的环是自环且深度不超过 （根结点深度为 ）。把这个基环树当成有根树是一样的。因此我们的问题转化为： 个点带标号，深度不超过 的有根树森林的计数。

考虑 个点带标号深度不超过 的有根树，假设它的生成函数是 。

考虑递推求 。深度不超过 的有根树，实际上就是深度不超过 的若干棵有根树，把它们的根结点全部连到一个结点上去。因此

那么答案的指数生成函数就是 。求它的第 项即可。

Lust

给你一个 个数的序列 ，和一个初值为 的变量 ，要求你重复以下操作 次：

• 在 中等概率随机选择一个 。
• 令 加上 。
• 令 减一。

求 次操作后 的期望。

。 假设 次操作后 减少了 ，那么实际上

因此实际上我们的问题转化为，求 次操作后 的期望。

不妨考虑计算每种方案的的 的和，最后除以 。

而 次操作序列中，要使得 出现了 次的方案数是

这与指数生成函数乘法的系数类似。

设 的指数生成函数是

那么答案就是

为了快速计算答案，我们需要将 转化为封闭形式：

因此我们得到

其中 是一个 次多项式，可以暴力计算出来。假设它的展开式是 ，那么

计算这个多项式的 项系数即可。