本节对应原书 PDF 第 256–258 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
上一节已经看到生成函数在组合计数问题中的广泛应用，本节将进一步引入指数型生成函数，并讨论它在有序计数中的应用.
定义 10.7 设 {a_n} 为序列，称
G_e(x)=\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}
为 {a_n} 的指数生成函数.
解读：普通生成函数把 a_n 挂在 x^n 上，指数生成函数则把 a_n 挂在 x^n/n! 上.多出的这个 n! 正是为「有序」准备的：排列计数天然带阶乘，除以 n! 之后乘法才能直接对应"先分成两组、各组内部排列"的拼装过程.
例 10.27 给定正整数 m，a_n=P(m,n)，则 {a_n} 的指数生成函数为
G_e(x)=\sum_{n=0}^{\infty}P(m,n)\frac{x^n}{n!}=\sum_{n=0}^{\infty}\frac{m!}{n!(m-n)!}x^n=\sum_{n=0}^{m}\binom{m}{n}x^n=(1+x)^m
不难看出，(1+x)^m 既是集合组合数序列 {C(m,n)} 的普通生成函数，也是集合排列数序列 {P(m,n)} 的指数生成函数.
解读：同一个 (1+x)^m 同时扮演两个角色，是本节最该记住的一句话.取 x^n 的系数：按普通生成函数读出来是 C(m,n)，按指数生成函数读出来（乘回 n!）是 P(m,n).
例 10.28 设 b_n=1，则 {b_n} 的指数生成函数为
G_e(x)=\sum_{n=0}^{\infty}\frac{x^n}{n!}=\mathrm{e}^x
与普通生成函数类似，指数生成函数具有下述重要的性质.
设数列 {a_n}，{b_n} 的指数生成函数分别为 A_e(x) 和 B_e(x)，则
A_e(x)\cdot B_e(x)=\sum_{n=0}^{\infty}c_n\frac{x^n}{n!}，\quad 其中 c_n=\sum_{k=0}^{n}\binom{n}{k}a_kb_{n-k}
证明
\begin{aligned}
\sum_{n=0}^{\infty}c_n\frac{x^n}{n!} &= A_e(x)\cdot B_e(x)=\sum_{k=0}^{\infty}a_k\frac{x^k}{k!}cdotsum_{l=0}^{\infty}b_l\frac{x^l}{l!} \
&= \sum_{n=0}^{\infty}x^nsum_{k=0}^{n}\frac{a_k}{k!}\cdot\frac{b_{n-k}}{(n-k)!}=\sum_{n=0}^{\infty}\frac{x^n}{n!}\sum_{k=0}^{n}\frac{n!}{k!(n-k)!}a_kb_{n-k} \
&= \sum_{n=0}^{\infty}\frac{x^n}{n!}\sum_{k=0}^{n}\binom{n}{k}a_kb_{n-k}
\end{aligned}
因此 c_n=sumlimits_{k=0}^{n}\binom{n}{k}a_kb_{n-k}.
解读：c_n 里的 \binom{n}{k} 是把 n 个带标签的对象先选出 k 个交给 a、剩下 n-k 个交给 b 的方式数——这正是普通生成函数卷积里没有的那一项，也是指数生成函数能处理"带标签对象"的原因.
使用指数生成函数可以求解多重集的排列问题.
定理 10.8 设 S={n_1\cdot a_1,n_2\cdot a_2,\cdots,n_kcdot a_k} 为多重集，则 S 的 r 排列数的指数生成函数为
G_e(x)=f_{n_1}(x)f_{n_2}(x)\cdots f_{n_k}(x)
其中
f_{n_i}(x)=1+x+\frac{x^2}{2!}+\cdots+\frac{x^{n_i}}{n_i!}\quad i=1,2,\cdots,k
证明 考察上述指数生成函数展开式中 x^r 的项，它是由 k 个因式的乘积构成的，并具有下述形式：
\frac{x^{m_1}}{m_1!}\frac{x^{m_2}}{m_2!}\cdots\frac{x^{m_k}}{m_k!}
其中 \frac{x^{m_i}}{m_i!} 来自 f_{n_i}(x).注意到 m_1,m_2,\cdots,m_k 满足下述不定方程
\begin{aligned}
m_1+m_2+\cdots+m_k &= r \
0\leqslant m_ileqslant n_i, \quad i=1,2,\cdots,k
\end{aligned}
\tag{10.4}
即
\frac{x^{m_1+m_2+\cdots+m_k}}{m_1!m_2!\cdots m_k!}=\frac{x^r}{r!}\frac{r!}{m_1!m_2!\cdots m_k!}
因此
a_r=\sum\frac{r!}{m_1!m_2!\cdots m_k!}
其中求和是对满足方程(10.4)的一切非负整数解来求.一个非负整数解对应了 S 的一个子多重集 {m_1\cdot a_1,m_2\cdot a_2,\cdots,m_kcdot a_k}，即 S 的一个 r 组合，而该组合的全排列数是 \frac{r!}{m_1!m_2!\cdots m_k!}，因此 a_r 代表了 S 的所有 r 排列数.
解读：因式 f_{n_i}(x) 里第 m_i 项 \frac{x^{m_i}}{m_i!} 就是"第 i 种字母取 m_i 个"这一事件的记账；多个因式相乘后 x^r 的系数自动汇总了所有满足 m_1+\cdots+m_k=r 的取法，而 \frac{r!}{m_1!\cdots m_k!} 恰好是这些字母的排列数.
例 10.29 由 1,2,3,4 组成的 5 位数中，要求 1 出现不超过 2 次，但不能不出现，2 出现不超过 1 次，3 出现至多 3 次，4 出现偶数次.求这样的 5 位数个数.
解
G_e(x)=\left(\frac{x}{1!}+\frac{x^2}{2!}
\right)(1+x)\left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}
\right)\left(1+\frac{x^2}{2!}+\frac{x^4}{4!}
\right)
=\left(x+5\frac{x^2}{2!}+18\frac{x^3}{3!}+64\frac{x^4}{4!}+215\frac{x^5}{5!}+\cdots
\right)
N=215
解读：四个因式依次对应数字 1、2、3、4 的出现次数限制：1 的因式缺了常数项（不能不出现）、最高只到 \frac{x^2}{2!}；2 的因式只有 1+x；4 的因式只留偶数次幂.所求是 5 位数个数，所以只取 \frac{x^5}{5!} 的系数再乘回 5!，即 215.
例 10.30 红、白、蓝涂色 1\times n 的方格，要求偶数个为白色，问有多少种方案？
解
G_e(x)=\left(1+\frac{x^2}{2!}+\cdots
\right)\left(1+x+\frac{x^2}{2!}+\cdots
\right)^2
=\frac{1}{2}(\mathrm{e}^x+\mathrm{e}^{-x})\mathrm{e}^{2x}
=\frac{1}{2}\mathrm{e}^{3x}+\frac{1}{2}\mathrm{e}^x
=\frac{1}{2}\sum_{n=0}^{\infty}3^n\frac{x^n}{n!}+\frac{1}{2}\sum_{n=0}^{\infty}\frac{x^n}{n!}
=\sum_{n=0}^{\infty}\frac{3^n+1}{2}\frac{x^n}{n!}
a_n=\frac{3^n+1}{2}
解读：把"偶数个白格"写成 \frac{1}{2}(\mathrm{e}^x+\mathrm{e}^{-x})，是指数生成函数处理奇偶约束的标准手法——它等于 \cosh x，只保留 x 的偶次幂项.红、蓝两色没有限制，各贡献一个 \mathrm{e}^x.