指数生成函数

指数生成函数（exponential generating function）把数列 $(a_n{)}_{n\ge 0}$ 编码为 $\sum _{n\ge 0}{a}_n{x}^n/n!$。阶乘使乘法自然对应“先分配不同标签，再分别构造”的计数。因此它常用于带标签组合对象；名称并不表示所有这类函数都是某个简单指数函数。

例如，把 $n$ 个有不同编号的物品分成红、蓝两类，允许一类为空。若恰有 $k$ 个红物品，先从 $n$ 个标签中选出这 $k$ 个，有 $(\genfrac{}{}{0ex}{}{n}{k})$ 种，总数为 $\sum _k(\genfrac{}{}{0ex}{}{n}{k})=2^n$。红类和蓝类各自只有一种“无额外结构的集合”，它们的指数生成函数都是 $e^x$，相乘得到 $e^{2x}$，其 $x^n/n!$ 系数恰为 $2^n$。

系数与乘法规则

在实数或有理数系数的形式幂级数中，定义 $$A(x)=\sum _{n\ge 0}{a}_n\frac{x^n}{n!},a_n=n![x^n]A(x).$$ 符号 $[x^n]$ 取普通幂次系数，所以不能漏乘 $n!$。形式级数只要求逐项代数有意义，不先要求解析收敛。

若 $C(x)=A(x)B(x)$，展开并收集总次数 $n$： $$[x^n]C(x)=\sum _{k=0}^n\frac{a_k{b}_{n-k}}{k!(n-k)!},c_n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a_k{b}_{n-k}.$$ 这是完整的乘法公式。组合解释中先选哪 $k$ 个标签用于第一结构，再在两份标签上分别选结构；两个部分角色有先后区别，因此没有再除二。若把两个无序同类部分当作有序乘积，就会重复计数，必须另外处理交换对称性。

普通生成函数的乘积只有 $\sum _k{a}_k{b}_{n-k}$，它没有自动提供标签分配的二项式系数。这正是开头红蓝问题用指数形式的原因。

单点与配对构成的排列

考虑只由不动点和互换对组成的排列，即作用两次回到原位的排列。设 $a_n$ 为 $n$ 个不同标签上的这种排列数。若有 $j$ 个互换对，先选出 $2j$ 个标签，再把它们分成无序对。将这 $2j$ 个标签排成一列共有 $(2j)!$ 种；每对内部交换会重复 $2^j$ 次，各对换序又重复 $j!$ 次，故 $$a_n=\sum _{j=0}^{\lfloor n/2\rfloor }\frac{n!}{(n-2j)!2^{j}j!}.$$ 除以 $n!$ 后对 $n$ 求和，令 $r=n-2j$，得到 $$A(x)=\left(\sum _{r\ge 0}\frac{x^r}{r!}\right)\left(\sum _{j\ge 0}\frac{(x^2/2{)}^j}{j!}\right)=\exp (x+x^2/2).$$ 对每个固定次数，只涉及有限个 $(r,j)$，所以形式级数重组合法，不需要交换无穷数值积分或极限。

当 $n=4$，零、一、二个配对分别贡献 $1,6,3$，总数十。例如二对情形为 $12|34,13|24,14|23$。直接展开 $e^x{e}^{x^2/2}$，$x^4$ 系数为 $1/24+1/4+1/8=10/24$，乘 $4!$ 回得十，而不是 $10/24$ 个对象。

变式。 五个标签时，有零、一、二个配对，贡献 $1,(\genfrac{}{}{0ex}{}{5}{2})=10,(\genfrac{}{}{0ex}{}{5}{4})\cdot 3=15$，故 $a_5=26$。也可指定标签一：它若不动，余下有 $a_4$ 种；若与某个其他标签互换，有四种伙伴和 $a_3=4$ 种余下结构，所以 $a_5=a_4+4a_3=10+16=26$。两个独立计数互相核对。

微分与收敛范围

形式微分给出 $A^{\prime }(x)=\sum _{n\ge 0}{a}_{n+1}{x}^n/n!$；乘以 $x$ 则对应新数列 $n{a}_{n-1}$，与普通生成函数的移位系数不同。配对例中 $A^{\prime }=(1+x)A$，比较系数得 $a_{n+1}=a_n+n{a}_{n-1}$，与指定一个标签的分类计数一致。

阶乘分母不保证解析收敛。例如 $a_n=(n!{)}^2$ 时，指数生成函数的项为 $n!x^n$，对任意 $x\ne 0$，相邻项绝对值之比为 $(n+1)|x|$，项不趋零，收敛半径为零。但它仍是合法形式幂级数。需要把变量代入数值、求解析导数或作渐近分析时，须另查收敛条件；纯粹系数运算与数值函数评价是两种使用方式。