Bóna · 枚举与解析组合学导论 · 第 3 章 生成函数

3.5　另一类生成函数A different type of generating functions

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

虽然普通生成函数（ordinary generating function）与指数生成函数（exponential generating function）是实际中最常用的两类生成函数，但它们并不是枚举中唯一有用的生成函数。有兴趣的读者可以在文献 [84] 中找到各式各样的其他生成函数。这里我们只再介绍一种类型——双重指数生成函数（doubly exponential generating function）；在后面某一章里我们会用到它。

本节目标到目前为止，我们学过的生成函数都是把数列 \(\{a_n\}\) 的第 \(n\) 项装到 \(x^n\) 的系数上：普通生成函数除以 \(1\)，指数生成函数除以 \(n!\)。本节要解决的问题是：当一个数列增长得太快，连指数生成函数都“压不住”时怎么办？答案是把每一项再除以一个 \(n!\)，也就是除以 \((n!)^2\)，这就得到“双重指数生成函数”。我们用它来求一个递推数列的通项公式。

三类生成函数的“分母”一眼对照（数列同为 \(\{a_n\}\)）：

名称 第 n 项前的因子 通项形式 普通 x^n / 1 Σ aₙ xⁿ 指数 x^n / n! Σ aₙ xⁿ/n! 双重指数 x^n / (n!)² Σ aₙ xⁿ/(n!)²
分母越大，对“大 \(n\)”的压制越强，能驯服增长越快的数列。
例 3.40 设 \(a_0=1\)，且当 \(n\ge 1\) 时 \(a_n=n^2a_{n-1}+n!\)。求 \(a_n\) 的显式公式。

稍作尝试便会发现，我们目前学过的两种生成函数对此情形都无济于事：这个数列增长得太快，即使是指数生成函数的技巧也压不住它。因此，我们定义 \[A(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!^2},\] 并称 \(A(x)\) 为数列 \(\{a_n\}_{n\ge 0}\) 的双重指数生成函数（doubly exponential generating function）。

先动手算几项，看它有多快 用递推 \(a_n=n^2a_{n-1}+n!\) 逐项计算：
  1. \(a_0=1\)（题目给定）。
  2. \(a_1=1^2\cdot a_0+1!=1+1=2\)。
  3. \(a_2=2^2\cdot a_1+2!=4\cdot 2+2=10\)。
  4. \(a_3=3^2\cdot a_2+3!=9\cdot 10+6=96\)。
  5. \(a_4=4^2\cdot a_3+4!=16\cdot 96+24=1560\)。
每一项都被前一项乘上 \(n^2\)，再加一个阶乘 \(n!\)。它比 \(n!\) 还快，所以指数生成函数（分母只有 \(n!\)）不够；要用分母 \((n!)^2\) 的双重指数生成函数才能把它“收敛化”。
为什么偏偏除以 \((n!)^2\)关键在递推里的因子 \(n^2\)。注意 \(n!=n\cdot(n-1)!\)，于是 \(n!^2=n^2\,(n-1)!^2\)，也就是 \[\frac{n^2}{n!^2}=\frac{1}{(n-1)!^2}.\] 选 \((n!)^2\) 作分母，就能让递推中的 \(n^2\) 被恰好抵消，把 \(a_{n-1}\) 的项整理成“移位后的同一个 \(A(x)\)”。下面就会看到这一步。

余下的部分并不困难。我们把例 3.40 的递推关系两边同乘 \(x^n/n!^2\)，再对所有 \(n\ge 1\) 求和。得到 \[\sum_{n\ge 1}a_n\frac{x^n}{n!^2}=\sum_{n\ge 1}a_{n-1}\frac{x^n}{(n-1)!^2}+\sum_{n\ge 1}\frac{x^n}{n!},\] 或者说，在两边都辨认出 \(A(x)\)，便有 \[A(x)-1=xA(x)+e^x-1,\] \[A(x)=\frac{e^x}{1-x}.\]

把上面这串等式逐项拆开看
  1. 左边。 \(\displaystyle\sum_{n\ge 1}a_n\frac{x^n}{n!^2}\) 就是 \(A(x)\) 去掉 \(n=0\) 那一项（\(a_0x^0/0!^2=1\)），所以左边 \(=A(x)-1\)。
  2. 右边第一项（含 \(n^2a_{n-1}\)）。 用上面算好的 \(\dfrac{n^2}{n!^2}=\dfrac{1}{(n-1)!^2}\)： \[\sum_{n\ge 1}n^2a_{n-1}\frac{x^n}{n!^2}=\sum_{n\ge 1}a_{n-1}\frac{x^n}{(n-1)!^2}.\] 令 \(m=n-1\)，提出一个 \(x\)： \[=x\sum_{m\ge 0}a_m\frac{x^m}{m!^2}=x\,A(x).\]
  3. 右边第二项（含 \(n!\)）。 \(\dfrac{n!}{n!^2}=\dfrac{1}{n!}\)，于是 \[\sum_{n\ge 1}n!\,\frac{x^n}{n!^2}=\sum_{n\ge 1}\frac{x^n}{n!}=e^x-1,\] 这里用到了 \(e^x=\sum_{n\ge 0}x^n/n!\)，减去 \(n=0\) 的那一项 \(1\)。
  4. 合起来。 \(A(x)-1=xA(x)+(e^x-1)\)。把含 \(A(x)\) 的项移到一边：\(A(x)-xA(x)=e^x\)，即 \((1-x)A(x)=e^x\)，所以 \[A(x)=\frac{e^x}{1-x}.\]
左边 A(x) − 1 n²aₙ₋₁ 项 → 移位 x·A(x) n! 项 → 指数 eˣ − 1 解出 eˣ/(1−x)
对递推两边乘 \(x^n/n!^2\) 求和后，三块各自变成 \(A(x)-1\)、\(xA(x)\)、\(e^x-1\)，一个一元一次方程就把 \(A(x)\) 解了出来。
从 \(A(x)\) 读出通项 \(a_n\)例 3.40 要的是 \(a_n\) 的显式公式。既然 \(A(x)=\dfrac{e^x}{1-x}\)，只需把它展开成幂级数，再对照定义 \(A(x)=\sum_n a_n\dfrac{x^n}{n!^2}\)，比较 \(x^n\) 的系数即可。
提取系数：两条已知级数相乘（柯西乘积）
  1. 把两个因子各自写成幂级数： \[e^x=\sum_{k\ge 0}\frac{x^k}{k!},\qquad \frac{1}{1-x}=\sum_{j\ge 0}x^j.\]
  2. 相乘时，凑出 \(x^n\) 需要 \(k+j=n\)，即 \(j=n-k\)，\(k\) 从 \(0\) 取到 \(n\)。每一项的系数是 \(\dfrac{1}{k!}\cdot 1\)。于是 \(x^n\) 的系数为 \[[x^n]\,\frac{e^x}{1-x}=\sum_{k=0}^{n}\frac{1}{k!}.\]
  3. 另一边，按定义 \([x^n]A(x)=\dfrac{a_n}{n!^2}\)。令两者相等： \[\frac{a_n}{n!^2}=\sum_{k=0}^{n}\frac{1}{k!}.\]
  4. 两边乘 \(n!^2\)，得到显式公式 \[\boxed{\,a_n=n!^2\sum_{k=0}^{n}\frac{1}{k!}\,}.\]♦
回代验证用公式重新算前几项，与前面递推算出的结果对照：
  1. \(a_0=0!^2\cdot\dfrac{1}{0!}=1\cdot 1=1\)。✓
  2. \(a_1=1!^2\left(\dfrac{1}{0!}+\dfrac{1}{1!}\right)=1\cdot(1+1)=2\)。✓
  3. \(a_2=2!^2\left(1+1+\dfrac{1}{2}\right)=4\cdot\dfrac{5}{2}=10\)。✓
  4. \(a_3=3!^2\left(1+1+\dfrac12+\dfrac16\right)=36\cdot\dfrac{8}{3}=96\)。✓
公式与递推完全吻合，说明双重指数生成函数确实把这个增长极快的数列“一次性解开”了。
eˣ 的各项： x⁰/0! x¹/1! x²/2! x³/3! … 1/(1−x) 的各项： x⁰ x¹ x² x³ … 要凑出 x³ ： x⁰·x³ + x¹·x² + x²·x¹ + x³·x⁰ 系数 = 1/0! + 1/1! + 1/2! + 1/3! = Σₖ₌₀³ 1/k!
柯西乘积（Cauchy product）：要得到 \(x^n\)，就把指数 \(k\) 与 \(n-k\) 配成一对求和，系数 \(\sum_{k=0}^n 1/k!\) 正是这样来的。

由此，例 3.40 中那个用普通和指数生成函数都难以处理的快速增长数列，通过双重指数生成函数就得到了简洁的封闭解。这正说明：除普通生成函数与指数生成函数之外，针对不同的增长速度，还有其他类型的生成函数可供选用——选对“分母”，递推就能化为可解的方程。

返回 全书目录