形如 $F(x)=\sum_{n=0}^{\infty}a_n\frac {x^n}{n!}$ 的函数， $a_n$ 可以提供关于这个序列的信息，一般用于解决有标号组合计数问题。

$$F(x)=\sum_{n=0}^{\infty}a_n\frac {x^n}{n!},G(x)=\sum_{n=0}^{\infty}b_n\frac {x^n}{n!}$$

$$F(x)G(x)=\sum_{n=0}^{\infty}\sum_{i=0}^n a_ib_{n-i}\frac {x^n}{i!(n-i)!}=\sum_{n=0}^{\infty}\sum_{i=0}^n {n\choose i}a_ib_{n-i}\frac {x^n}{n!}$$

$$\sum_{n=0}^{\infty}k^n\frac {x^n}{n!}=e^{kx}$$

$$\sum_{n=0}^{\infty}n^{\underline k}\frac {x^n}{n!}=x^ke^x$$

洛谷p5748

定义贝尔数 $w_n$ 表示将集合 $\{1,2\cdots n\}$ 划分为若干个不相交非空集合的方案数，求 $w_n$。

假设将 $n$ 化分到一个大小为 $i$ 的集合，不难得出递推式

$$w_n=[n==0]+\sum_{i=1}^{n} {n-1\choose i-1}w_{n-i}$$

构造 $F(x)=\sum_{n=0}^{\infty}w_n\frac {x^n}{n!},G(x)=\sum_{n=0}^{\infty}\frac {x^n}{n!}=e^x$，于是有

$$F(x)=1+\int F(x)G(x)\mathrm{d}x=1+\int F(x)e^x\mathrm{d}x$$

接下来考虑求解 $F(x)$

$$\mathrm{d}F(x)=F(x)e^x\mathrm{d}x$$

$$\frac {\mathrm{d}F(x)}{F(x)}=e^x\mathrm{d}x$$

$$\ln F(x)=e^x+C$$

将 $F(0)=1$ 代入，得 $F(x)=\exp (e^x-1)$，于是 $w_n=[\frac {x^n}{n!}]F(x)$。

考虑对结果的解释，$e^x-1=\sum_{n=1}^{\infty}a_n\frac {x^n}{n!}(a_n=1)$ 可以理解为将所有 $n$ 个元素化为为一个集合的方案数 $a_n$ 的 $\text{EGF}$。

$\exp (e^x-1)=\sum_{i=0}^{\infty} \cfrac {A^i(x)}{i!}$ 式子中 $\sum_{i=0}^{\infty}$ 可以理解为枚举最终划分的集合数 $i$。

$A^i(x)$ 可以理解为将所有元素划分为 $i$ 个非空集合，$i!$ 可以理解为划分的集合之间无序所以除以全排列数。

类似的，设 $n$ 个点带标号生成树的 $\text{EGF}$ 为 $F(x)$，则 $n$ 个点带标号生成森林的 $\text{EGF}$ 为 $\exp F(x)$。

其中 $n$ 个点带标号生成树的 $\text{EGF}$ 容易求得为 $\sum_{n=0}^{\infty} n^{n-2}\frac {x^n}{n!}$，所以取 $\exp$ 即可快速求得 $n$ 个点带标号生成森林的 $\text{EGF}$。

设 $n$ 个点带标号无向连通图的 $\text{EGF}$ 为 $F(x)$，则 $n$ 个点带标号无向图的 $\text{EGF}$ 为 $\exp F(x)$。

其中 $n$ 个点带标号无向图的 $\text{EGF}$ 容易求得为 $\sum_{n=0}^{\infty} 2^{n(n-1)/2}\frac {x^n}{n!}$，所以取 $\ln$ 即可快速求得 $n$ 个点带标号无向连通图的 $\text{EGF}$。

定义错排数 $a_i$ 等于长度为 $n$ 且 $p_i\neq i$ 的置换个数，求错排数 $a_n$。

$p_i\neq i$ 等价于不含长度为 $1$ 的置换环，考虑所有元素处于同一个置换环时的 $\text{EGF}$。

$$\sum_{n=2}^{\infty}(n-1)!\frac {x^n}{n!}=\sum_{n=2}^{\infty}\frac {x^n}n=-\ln (1-x)-x$$

错排等价于将置换划分为若干个长度不为 $1$ 的置换环，于是错排数的 $\text{EGF}$ 即为 $\exp (-\ln (1-x)-x)$。

求满足 $\underbrace{f\circ f\circ\cdots\circ f}_{k}=\underbrace{f\circ f\circ\cdots\circ f}_{k-1}$ 的长度为 $n$ 的置换个数。

建图，连有向边 $i\to f(i)$。由于 $\underbrace{f\circ f\circ\cdots\circ f}_{k}=\underbrace{f\circ f\circ\cdots\circ f}_{k-1}$，该图显然存在自环，且所有点 $k-1$ 步内一定到达自环点。

而该图只有 $n$ 条边，于是该图显然只存在一个环，于是只存在一个自环点，设其为根节点，于是忽略自环则该图恰好为一个内向树。

于是问题转化为求 $n$ 个点带标号的深度不超过 $k$ (假设根节点深度为 $1$)的生成树的 $\text{EGF}$，设其为 $F_k(x)$。

显然这等价于选择一个点作为根节点然后取 $n-1$ 个点带标号的深度不超过 $k-1$ 的生成森林向其连边。

于是有 $[\frac {x^n}{n!}]F_k(x)=n[\frac {x^{n-1}}{(n-1)!}]\exp F_{k-1}(x)=[\frac {x^n}{n!}]\exp xF_{k-1}(x)$。

即 $F_k(x)=\exp xF_{k-1}(x)$，边界条件 $F_1(x)=x$。