Bóna · 枚举与解析组合学导论 · 第 7 章 解析组合学

7.3　更精确的渐近More precise asymptotics

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

有时我们能把渐近结果细化到比多项式精度（polynomial precision）还要精确的程度。下面我们考虑两种可以做到这一点的情形。

本节目标上一节我们只能说出系数 \(a_n\) 的增长阶（例如形如 \(Cn^2 2^n\)）。本节要更进一步：在合适的条件下，把系数的确切极限值算出来——不必先求出每个 \(a_n\)，就能直接得到 \(\displaystyle\lim_{n\to\infty}a_n\)。核心工具是定理 7.37：整函数除以 \((1-x)\) 时，其系数收敛到该整函数在 \(x=1\) 处的值。

7.3.1　整函数除以 \((1-x)\)

某些幂级数（power series）的系数数列本身是收敛的，并且我们能够在不逐个算出这些系数的情况下，求出该数列的极限。

回忆：若一个排列（permutation）不含任何 1-环（1-cycle，即不动点），就称它为错位排列（derangement）。类似地，若一个排列既不含 1-环也不含 2-环（2-cycle），就称它为2-错位排列（2-derangement）。设 \(D_{2,n}\) 为长度 \(n\) 的 2-错位排列的个数。我们能说出比值 \(D_{2,n}/n!\) 的什么信息？换句话说，随机选取一个长度为 \(n\) 的排列，它恰好是 2-错位排列的概率是多少？

把长度 \(n\) 的排列拆成若干环；2-错位排列只允许长度 ≥ 3 的环 3-环 ✓ 允许 2-环 ✗ 禁止 1-环（不动点）✗ 禁止
2-错位排列：把排列写成不相交的若干环，要求每个环长度至少为 3。最短的合法环是 3-环，例如把 \(\{1,2,3\}\) 排成 \(1\to2\to3\to1\)。

设 \(\displaystyle D_2(x)=\sum_{n\ge 0}D_{2,n}\frac{x^n}{n!}\) 为数列 \(D_{2,n}\) 的指数生成函数（exponential generating function），其中约定 \(D_{2,0}=1\)。我们可以用指数公式（exponential formula）得到 \(D_2(x)\)。事实上，要得到一个被 \(D_{2,n}\) 计数的排列，需要先把 \([n]\) 划分成若干大小至少为 \(2\) 的块，再在每个大小为 \(k\) 的块上放置一个 \(k\)-环。当 \(k\ge 3\) 时有 \((k-1)!\) 种放法，否则有 \(0\) 种。这导出生成函数

\[A(x)=\sum_{k\ge 3}\frac{(k-1)!}{k!}\,x^k=\sum_{k\ge 3}\frac{x^k}{k}=\ln\frac{1}{1-x}-x-\frac{x^2}{2}.\]

因此，由指数公式得

\[\tag{7.24}D(x)=e^{A(x)}=\frac{e^{-x-\frac{x^2}{2}}}{1-x}.\]
例（A(x) 是怎么算出来的）
  1. 放环的方法数：在 \(k\) 个元素上排一个 \(k\)-环共有 \((k-1)!\) 种（先固定第一个元素，再排其余 \(k-1\) 个），所以“一个 \(k\)-环”这种连通结构对应的指数生成函数项是 \(\dfrac{(k-1)!}{k!}x^k\)。
  2. 约分：\(\dfrac{(k-1)!}{k!}=\dfrac{1}{k}\)，于是单环的生成函数是 \(\displaystyle\sum_{k\ge 3}\frac{x^k}{k}\)。
  3. 用已知级数 \(\displaystyle\sum_{k\ge 1}\frac{x^k}{k}=-\ln(1-x)=\ln\frac{1}{1-x}\)，再把不允许的 \(k=1\) 项 \(x\) 和 \(k=2\) 项 \(\dfrac{x^2}{2}\) 减掉，就得到 \(A(x)=\ln\dfrac{1}{1-x}-x-\dfrac{x^2}{2}\)。
  4. 指数公式说：若 \(A(x)\) 是“一个连通件”的指数生成函数，则“任意多个连通件拼成的整体”的指数生成函数是 \(e^{A(x)}\)。代入得 \(e^{A(x)}=e^{\ln\frac{1}{1-x}}\cdot e^{-x-\frac{x^2}{2}}=\dfrac{1}{1-x}\cdot e^{-x-\frac{x^2}{2}}\)，即 (7.24)。

于是我们得到了 \(D(x)\) 的显式表达式，可是该怎么用它呢？为数 \(D_{2,n}\) 写出一个显式公式太复杂了，因为 \(D(x)\) 的分子里含两个求和号，而再除以 \(1-x\) 又意味着一层新的求和。显然 \(D(x)\) 只有一个奇点（singularity），在 \(x=1\) 处；但这只说明 \(D(x)\) 的系数——也就是数 \(D_{2,n}/n!\)——的指数增长率（exponential growth rate）为 \(1\)。这并不太令人惊讶，因为所有收敛到正常数的数列其指数增长率都是 \(1\)。为了达成我们的目标，即求出 \(\displaystyle\lim_{n\to\infty}\frac{D_{2,n}}{n!}\)，我们需要学习一项新技术。下面的定理就是朝这个目标迈进的主要工具。

定理 7.37 设 \(f\) 为整函数（entire function），且 \[\frac{f(x)}{1-x}=\sum_{n\ge 0}a_n x^n.\] 则 \(a_n\sim f(1)\)。换言之，\(\displaystyle\lim_{n\to\infty}a_n=f(1)\)。
先读懂定理在说什么整函数是指在整个复平面上都收敛的幂级数 \(f(x)=\sum_{n\ge0}f_n x^n\)，例如 \(e^x,\ e^{-x},\ e^{-x-x^2/2}\) 都是整函数。把这样一个 \(f(x)\) 除以 \(1-x\)，新级数的系数 \(a_n\) 会稳定地趋向一个固定的数，而这个数恰好就是把 \(x=1\) 代进 \(f\) 得到的 \(f(1)=\sum_{n\ge0}f_n\)。
例（除以 \(1-x\) 在做什么）对任意级数 \(g(x)=\sum b_n x^n\)，乘以 \(\dfrac{1}{1-x}=1+x+x^2+\cdots\) 相当于做前缀求和： \[\frac{g(x)}{1-x}=\sum_{n\ge0}\Big(b_0+b_1+\cdots+b_n\Big)x^n.\] 所以 \(\dfrac{f(x)}{1-x}\) 的第 \(n\) 个系数就是 \(f\) 的系数的前 \(n+1\) 项之和 \(f_0+f_1+\cdots+f_n\)。当 \(n\to\infty\) 时，这个部分和趋于 \(\sum_{k\ge0}f_k=f(1)\)。定理 7.37 正是这一观察的严格版本。
证明. 注意到 \[\tag{7.25}\frac{f(x)}{1-x}=\frac{f(x)-f(1)}{1-x}+\frac{f(1)}{1-x}=\frac{f(x)-f(1)}{1-x}+f(1)\sum_{n\ge0}x^n.\] 观察到函数 \(F(x)=\dfrac{f(x)-f(1)}{1-x}\) 是整函数。事实上，由于 \(f(x)\) 是整函数，它处处收敛，因此 \(f(x)=\sum_{n\ge0}f_n x^n\)，特别地 \(f(1)=\sum_{n}f_n\)。于是 \[\begin{aligned} F(x)&=\frac{f(x)-f(1)}{1-x}=\frac{\sum_{n\ge0}f_n(x^n-1)}{1-x}\\ &=-\sum_{n\ge0}f_n\big(1+x+\cdots+x^{n-1}\big)\\ &=\sum_{n\ge0}\Big(-\sum_{k\ge n+1}f_k\Big)x^n. \end{aligned}\] 在 \(F(x)\) 的最后这个形式里，所有系数都是收敛的和，因为连 \(\sum_{k\ge0}f_k=f(1)\) 都是有限的。出于同样的原因，部分（尾）和 \(\sum_{k\ge n+1}f_k\) 当 \(n\to\infty\) 时收敛到 \(0\)。 为证明我们的论断，现在比较 (7.25) 式最左端与最右端中 \(x^n\) 的系数。在最左端，按定义这个系数就是 \(a_n\)。最右端是两个被加项之和：第二个被加项对每个 \(x\) 的幂次都贡献系数 \(f(1)\)；而第一个被加项的系数数列（如我们刚刚证明的）收敛到 \(0\)。故 \(a_n=f(1)+\big(\text{趋于 }0\big)\to f(1)\)。♦
证明里的关键代数：为什么 \(\dfrac{x^n-1}{1-x}=-(1+x+\cdots+x^{n-1})\)
  1. 因式分解 \(x^n-1=(x-1)(x^{n-1}+\cdots+x+1)\)。这是熟悉的几何级数因式分解。
  2. 而分母 \(1-x=-(x-1)\)。
  3. 相除，约去 \((x-1)\)：\(\dfrac{x^n-1}{1-x}=\dfrac{(x-1)(1+x+\cdots+x^{n-1})}{-(x-1)}=-(1+x+\cdots+x^{n-1})\)。
  4. 因此每个 \(f_n\) 给系数 \(x^j\)（\(0\le j\le n-1\)）贡献 \(-f_n\)；把对 \(x^n\) 有贡献的所有项（即下标 \(k\ge n+1\) 的 \(f_k\)）收集起来，\(x^n\) 的系数就是 \(-\sum_{k\ge n+1}f_k\)。
值 n f(1) a_n（前缀和）
系数 \(a_n=f_0+f_1+\cdots+f_n\) 随 \(n\) 增大稳定逼近水平渐近线 \(f(1)\)；它与 \(f(1)\) 的差正是尾和 \(\sum_{k\ge n+1}f_k\)，趋于 \(0\)。
推论 7.38 当 \(n\) 趋于无穷时，随机选取的长度为 \(n\) 的排列是 2-错位排列的概率收敛到 \(e^{-3/2}\sim 0.22313\)。
证明. 只需对 \(f(x)=e^{-x-x^2/2}\) 应用定理 7.37。♦
例（把 \(f(1)\) 代进去算）由 (7.24)，\(\dfrac{D_{2,n}}{n!}\) 是 \(\dfrac{f(x)}{1-x}\) 的系数，其中 \(f(x)=e^{-x-x^2/2}\)。这是整函数，故由定理 7.37， \[\lim_{n\to\infty}\frac{D_{2,n}}{n!}=f(1)=e^{-1-\frac{1}{2}}=e^{-3/2}\approx 0.22313.\] 也就是说，对很大的 \(n\)，大约 \(22.3\%\) 的排列既没有不动点、也没有 2-环。

我们同样可以毫不费力地重新得到第 4 章证明过的结果，即：对很大的 \(n\)，长度为 \(n\) 的全部排列中大约有 \(1/e\) 是错位排列。事实上，若 \(D_n\) 表示长度为 \(n\) 的错位排列个数，我们在 (4.11) 中已见过 \[\sum_{n\ge0}D_n\frac{x^n}{n!}=\frac{e^{-x}}{1-x}.\] 于是对 \(f(x)=e^{-x}\) 应用定理 7.37，便得 \(\dfrac{D_n}{n!}\approx e^{-1}\)。

例（重新得到经典的 \(1/e\)）取 \(f(x)=e^{-x}\)，它是整函数，\(f(1)=e^{-1}\approx 0.3679\)。所以随机排列是错位排列的概率趋于 \(e^{-1}\)。这正是熟悉的“放错信封”问题答案，现在用统一的工具一行算出。
例 7.39 设 \(h_n\) 为如下操作的方法数：把 \([n]\) 划分成两个块 \(A\) 与 \(B\)（允许 \(B\) 为空，但 \(A\) 不能为空），然后取 \(A\) 的一个集合划分（partition），并取 \(B\) 中元素的一个排列（permutation）。求 \(\displaystyle\lim_{n\to\infty}\frac{h_n}{n!}\)。
（下面的求解用刚学到的定理 7.37 完成，作为本节技术的演练。）
  1. 写出 \(B\) 部分的指数生成函数：长度为 \(k\) 的集合上排列有 \(k!\) 个，故 \(\displaystyle\sum_{k\ge0}k!\frac{x^k}{k!}=\sum_{k\ge0}x^k=\frac{1}{1-x}\)。
  2. 写出 \(A\) 部分的指数生成函数：集合划分的指数生成函数是 \(e^{e^x-1}\)（贝尔数的指数生成函数）；由于 \(A\) 不能为空，去掉空集对应的常数项 \(1\)，得到 \(e^{e^x-1}-1\)。
  3. 把元素先分给 \(A\)、\(B\) 两块，再分别施加结构，这是一个乘积结构，故 \(\displaystyle\sum_{n\ge0}h_n\frac{x^n}{n!}=\big(e^{e^x-1}-1\big)\cdot\frac{1}{1-x}=\frac{f(x)}{1-x}\)，其中 \(f(x)=e^{e^x-1}-1\)。
  4. \(f(x)=e^{e^x-1}-1\) 是整函数（\(e^x\) 与 \(e^{(\cdot)}\) 的复合仍处处收敛），于是由定理 7.37， \[\lim_{n\to\infty}\frac{h_n}{n!}=f(1)=e^{e-1}-1\approx e^{1.71828}-1\approx 4.5746.\]
小结：本小节的解题套路
  1. 把待求计数对象的指数生成函数化成 \(\dfrac{f(x)}{1-x}\) 的形式——通常 \(1-x\) 来自“一个可有可无、内部为排列的部分”或“做前缀求和”。
  2. 验证分子 \(f(x)\) 是整函数（常见的 \(e^{\text{多项式}}\)、\(e^{e^x-1}\) 等都满足）。
  3. 直接代入 \(x=1\)：极限 \(\displaystyle\lim_{n\to\infty}a_n=f(1)\)。无需求出任何单个系数。

返回 全书目录