指数生成函数 | Codeboy's Blog

形式陈述

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

A(x)=\sum_{n\ge0}a_n\frac{x^n}{n!}.

它通常在特征零的系数域中使用。若 $a_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)=\sum_{n\ge0}a_{n+1}x^n/n!$ ，可编码移位递推。

直觉

分母 $n!$ 抵消标号集合在重新分配时产生的排列数，使“把一组标号拆给若干部件”的组合卷积直接变成普通乘法。因而指数生成函数不是为了分析方便任意改写，而是与标号对象的乘积规则精确匹配。求导会把一个标号挑出来作根，指数函数则对应由若干互不相交标号部件组成的集合。

例子与边界

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

若 $a_n=1$ 表示每个标号集上只有一种结构，则

A(x)=\sum_{n\ge0}\frac{x^n}{n!}=e^x.

两个独立标号结构类相乘时， $n$ 个标号先选 $k$ 个给第一类，系数出现 $\binom nk a_kb_{n-k}$ ，恰由 EGF 乘积还原。普通生成函数乘法没有这个二项式因子，因此不能在标号与无标号模型之间不加说明地互换。

推论与应用

序列经阶乘归一化嵌入幂级数，与标号乘法原理相容。错排、集合划分和标号树可用 EGF 统一推导；与普通生成函数相比，选择哪一种取决于对象组合时标号是否需要重新分配，而非仅取决于是否有闭式。

参考资料

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。

形式陈述 ​

反向链接

形式陈述