EGF：指数型生成函数

对于一个数列 \(<a_n>\)，定义其指数型生成函数（EGF）\(\hat{a}(x)=\displaystyle\sum_{n\ge 0}\dfrac{a_n}{n!}x^n\)。

例，排列数 \(p_i=i!\) 的 EGF：\(\hat{p}(x)=\displaystyle\sum_{n\ge 0}\dfrac{p_n}{n!}x^n=\sum_{n\ge 0}x^n=\dfrac{1}{1-x}\)。（最后一步错位相减）

圆排列 \(q_i=(i-1)!\) 的 EGD：\(\hat{q}(x)=\displaystyle\sum_{n\ge 1}\dfrac{(n-1)!}{n!}x^n=\sum_{n\ge 1}\dfrac{x^n}{n}=\ln \dfrac{1}{1-x}\)。

我们发现 \(\hat{p}(x)=\exp(\hat{q}(x))\)！

\(\exp(f(x))=\displaystyle\sum_{i\ge 0}\dfrac{f(x)^i}{i!}\)，这是一个复合函数。

定理：若 \(<a_n>\) 的 EGF 为 \(\hat{A}(x)\)，\(<b_n>\) 的 EGF 为 \(\hat{B}(x)\)，\(<c_n>\) 的 EGF 为 \(\hat{C}(x)\)，则 \(c_n=\displaystyle\sum_{i+j=n}(^n_i)a_ib_j\)。即 \(c\) 是 \(a,b\) 的二项式卷积结果。