形式陈述

对系数序列 $(a_n)_{n\ge0}$$(a_n{)}_{n\ge 0}$，指数生成函数定义为形式幂级数

$$ A(x)=\sum_{n\ge0}a_n\frac{x^n}{n!}. $$$$A(x)=\sum _{n\ge 0}{a}_n\frac{x^n}{n!}.$$

它通常在特征零的系数域中使用。若 $a_n$$a_n$ 计数大小为 $n$$n$ 的带标号对象，则乘法对应把标签集划分给有序的两个组件：

$$ A(x)B(x)=\sum_{n\ge0}\left(\sum_{k=0}^n\binom nk a_kb_{n-k}\right)\frac{x^n}{n!}. $$$$A(x)B(x)=\sum _{n\ge 0}\left(\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a_k{b}_{n-k}\right)\frac{x^n}{n!}.$$

导数满足 $A'(x)=\sum_{n\ge0}a_{n+1}x^n/n!$$A^{\prime }(x)=\sum _{n\ge 0}{a}_{n+1}{x}^n/n!$，可编码移位递推。

直觉

分母 $n!$$n!$ 抵消了给对象分配具体标签的排列数，因此指数生成函数天然适合带标号结构；普通生成函数更适合无标号或序列式组合。

例子与边界

集合排列数 $a_n=n!$$a_n=n!$ 的 EGF 为 $1/(1-x)$$1/(1-x)$；只有一个大小为 $n$$n$ 的“纯标签集合”时 $a_n=1$$a_n=1$，EGF 为 $e^x$$e^x$。EGF 只是编码工具，系数不必非负或具有组合意义。作为形式级数时不需要讨论收敛半径；作为解析函数使用求值、奇点或渐近时必须另行证明收敛。正特征环中 $n!$$n!$ 可能不可逆，标准定义需改写为除幂结构等更合适语言。

推论与应用

指数生成函数处理带标号树、排列、集合分拆、指数公式和 labelled product，并把二项卷积转化为普通乘法。

参考资料

• Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011，Ch. 1, exponential generating functions and labelled enumeration。
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009，Ch. II, labelled constructions and exponential generating functions。