指数生成函数 | Codeboy's Blog

形式陈述

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

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

更一般可在允许所有正整数除法的交换 $\mathbb Q$ -代数中使用。若 $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$ 个普通标号之外附加一个指定标号，后者不计入大小。若从现有的 $n$ 个标号中选一个作根且保持大小，计数为 $na_n$ ，对应的是 $xA'(x)$ 。两种操作的大小约定不同。

直觉

乘积中的 $\binom nk$ 有明确来源：先从 $n$ 个标签中选择 $k$ 个交给第一个组件，再分别放上 $a_k$ 与 $b_{n-k}$ 种结构。除以 $n!$ 后， $\binom nk/n!=1/(k!(n-k)!)$ ，恰好成为两个 EGF 系数的乘积。分母因此把“分配标签”纳入普通乘法，并没有让对象的标签消失。

求导把一个指定标签从大小计数中移出，乘回 $x$ 才是保持原大小的选根。对没有空对象的部件类 $B$ ，由 $j$ 个部件组成的无序集合对应 $B(x)^j/j!$ ：非空且互不相交的标签集使部件可以区分，忘掉部件顺序恰好除以 $j!$ 。对 $j\ge0$ 求和得到 $\exp(B(x))$ ；排除空部件还保证固定总大小时只有有限种分解。

例子与边界

集合排列数 $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$ 种选择，所以 EGF 是 $xe^x$ ，大小为零时没有选根对象。若附加一个不计入大小的指定标签，则仍只有一种结构，EGF 为 $e^x$ 。这个例子直接区分 $xA'(x)$ 与 $A'(x)$ 。普通生成函数的乘法没有二项卷积因子，不能在标号与无标号模型之间直接互换。

推论与应用

序列经阶乘归一化成为形式幂级数，与标号乘法原理相容。错排、集合划分和标号树可用 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。

形式陈述 ​

反向链接

形式陈述