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

7.2　多项式精度Polynomial precision

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

说明：本节所附的原文 PDF 仅含本小节的开篇（标题与引入段落），其后页面未包含在该文件中。下文先忠实翻译已给出的开篇文字，再以与本节主题完全一致的方式，用具体数字、分步推演和配图把“多项式精度”这一概念讲透——所用例子（中心二项式系数、斯特林公式、卡特兰数）都是标准且可独立验证的数学事实。

有时候，我们不仅能用“指数精度（exponential precision）”确定一个数列的增长速度，还能用“多项式精度（polynomial precision）”确定它，甚至能确定得更精确。在本节中，我们将看到这种现象的若干例子。

本节目标上一节我们只问“数列大约像 \(c^n\) 一样增长吗？”——也就是只抓住指数部分 \(c\)。本节要把精度再提高一档：除了指数底数 \(c\)，再把乘在前面的多项式（幂次）因子 \(n^{\theta}\) 也确定下来，写成形如 \[a_n \approx C\cdot c^{\,n}\cdot n^{\theta}\] 的样子。这一档精度就叫“多项式精度”。

1. 先回顾：什么是“指数精度”

在 7.1 节里，我们对一个正项数列 \(a_1,a_2,a_3,\dots\) 定义了它的指数增长率（exponential growth rate）：若极限

\[\lim_{n\to\infty} a_n^{\,1/n}=c,\]

存在，就说这个数列的指数增长率是 \(c\)。直观上，这相当于说“\(a_n\) 大致按 \(c^n\) 的速度变大”。

例（指数精度只看一个数）取 \(a_n=3^n+n^{10}\)。当 \(n\) 很大时，\(3^n\) 远远压过 \(n^{10}\)，所以 \[a_n^{1/n}=\big(3^n+n^{10}\big)^{1/n}\to 3.\] 也就是说，无论后面那一项是 \(n^{10}\) 还是 \(n^{100}\) 还是 \(5n^2\)，指数增长率都只报出一个数 \(3\)。指数精度看不见这些多项式大小的差别——这正是我们需要“更高一档精度”的原因。
n（越往右越大） 3ⁿ（指数） n¹⁰（多项式）
指数函数 \(3^n\)（蓝实线）最终把任何多项式 \(n^{10}\)（红虚线）远远甩在后面。所以 \(a_n^{1/n}\) 只“认得”指数底数 \(3\)，认不出多项式那一项。

2. 为什么需要“多项式精度”

很多组合计数得到的数列，恰好不是纯粹的 \(c^n\)，而是 \(c^n\) 再乘上一个幂次因子 \(n^{\theta}\)（\(\theta\) 可以是负数，如 \(-\tfrac12\)、\(-\tfrac32\)）。这个幂次因子虽然比指数项小，却对“实际数值”影响巨大，也常常正是我们想知道的信息。下面用一个最经典的数列来看清这一点。

记号：中心二项式系数所谓中心二项式系数（central binomial coefficient）就是 \[\binom{2n}{n}=\frac{(2n)!}{n!\,n!}.\] 它数的是“从 \(2n\) 个对象里取出 \(n\) 个”的方法数，是组合学里出现得最频繁的数列之一。
例（先把前几项算出来）
\(n\)1234510
\(\binom{2n}{n}\)262070252184756
\(4^n\)4166425610241048576
可以看出 \(\binom{2n}{n}\) 一直比 \(4^n\) 小一截，而且 \(n\) 越大、差距占比越稳定地变化。它的指数底数显然是 \(4\)，但“小的那一截”到底是多少？这正是多项式精度要回答的。

3. 求出指数底数：先做“指数精度”

先验证 \(\binom{2n}{n}\) 的指数增长率确实是 \(4\)。一个简单的夹逼能说明问题：在二项式定理 \((1+1)^{2n}=\sum_{k=0}^{2n}\binom{2n}{k}=4^n\) 中，中心项 \(\binom{2n}{n}\) 是这 \(2n+1\) 个加项里最大的一项。于是

\[\frac{4^n}{2n+1}\le \binom{2n}{n}\le 4^n.\]
  1. 左不等式：\(4^n\) 是 \(2n+1\) 个加项之和，每项都不超过最大项 \(\binom{2n}{n}\)，所以 \(4^n\le(2n+1)\binom{2n}{n}\)，即 \(\binom{2n}{n}\ge \dfrac{4^n}{2n+1}\)。
  2. 右不等式：\(\binom{2n}{n}\) 只是那一堆非负加项中的一项，自然 \(\le\) 全部之和 \(4^n\)。
  3. 两边开 \(n\) 次方：\(\left(\dfrac{4^n}{2n+1}\right)^{1/n}=4\cdot(2n+1)^{-1/n}\to 4\)（因为 \((2n+1)^{1/n}\to1\)），而右边 \((4^n)^{1/n}=4\)。
  4. 夹逼得到 \(\displaystyle\lim_{n\to\infty}\binom{2n}{n}^{1/n}=4\)。♦

所以指数精度告诉我们：\(\binom{2n}{n}\) 的指数底数是 \(4\)。但上表里 \(184756\) 和 \(4^{10}=1048576\) 差了将近 \(5.7\) 倍——只报一个“\(4\)”显然没把这个差别说清楚。我们要往前再走一步。

4. 求出多项式因子：用斯特林公式

把指数因子之外的幂次因子也确定下来的标准工具，是斯特林公式（Stirling's formula）：

\[n!\;\sim\;\sqrt{2\pi n}\,\left(\frac{n}{e}\right)^{n},\]

这里“\(\sim\)”表示两边之比当 \(n\to\infty\) 时趋于 \(1\)。把它代入 \(\binom{2n}{n}=\dfrac{(2n)!}{(n!)^2}\)：

推演.
  1. 分子：\((2n)!\sim\sqrt{2\pi\cdot 2n}\,\left(\dfrac{2n}{e}\right)^{2n}=\sqrt{4\pi n}\,\left(\dfrac{2n}{e}\right)^{2n}\)。
  2. 分母：\((n!)^2\sim\left[\sqrt{2\pi n}\,\left(\dfrac{n}{e}\right)^{n}\right]^2=2\pi n\,\left(\dfrac{n}{e}\right)^{2n}\)。
  3. 相除，先看那个 \(e\) 的幂——分子分母的 \(e^{-2n}\) 正好抵消，剩下幂的部分是 \(\dfrac{(2n)^{2n}}{n^{2n}}=2^{2n}=4^{n}\)。
  4. 再看根号与系数部分：\(\dfrac{\sqrt{4\pi n}}{2\pi n}=\dfrac{2\sqrt{\pi n}}{2\pi n}=\dfrac{1}{\sqrt{\pi n}}\)。
  5. 合起来： \[\binom{2n}{n}\;\sim\;\frac{4^{n}}{\sqrt{\pi n}}.\] ♦
结论（多项式精度） \[\boxed{\;\binom{2n}{n}\sim \dfrac{4^{n}}{\sqrt{\pi n}}=\dfrac{1}{\sqrt{\pi}}\cdot 4^{n}\cdot n^{-1/2}.\;}\] 这就是“多项式精度”的样子：指数底数 \(c=4\)，多项式（幂次）因子 \(n^{\theta}\) 中的 \(\theta=-\tfrac12\)，常数 \(C=\tfrac1{\sqrt\pi}\)。
例（用数字检验这个估计有多准）
\(n\)真实值 \(\binom{2n}{n}\)估计 \(4^n/\sqrt{\pi n}\)比值
5252≈ 258.40.975
10184756≈ 1870760.988
50≈ 1.009×10²⁹≈ 1.011×10²⁹0.9975
比值随 \(n\) 增大稳稳地趋向 \(1\)——这正是 \(\sim\) 的含义。多项式精度不仅说对了“缩小的那一截”由 \(\tfrac1{\sqrt{\pi n}}\) 给出，还能给出相当准确的近似数值。
回头看：为什么 \(a_n^{1/n}\) 收敛得那么慢第 3 节里我们算 \(\binom{10}{5}^{1/5}\approx3.02\)、\(\binom{20}{10}^{1/10}\approx3.36\)，明明极限是 \(4\)，怎么离 \(4\) 还差挺远？现在用多项式精度一眼看穿： \[\binom{2n}{n}^{1/n}\sim\left(\frac{4^n}{\sqrt{\pi n}}\right)^{1/n}=4\cdot(\pi n)^{-1/(2n)}.\] 那个 \((\pi n)^{-1/(2n)}\) 趋于 \(1\) 但非常慢（\(n=10\) 时才约 \(0.84\)）。正是被指数精度忽略掉的多项式因子 \(n^{-1/2}\)，造成了 \(n\) 次根收敛缓慢。这说明多项式精度确实抓住了更细的信息。
比值 = 1（目标） n=5 n=10 n=50 n→∞
真实值 \(\binom{2n}{n}\) 与多项式精度估计 \(4^n/\sqrt{\pi n}\) 的比值（蓝点）稳稳地向 \(1\)（绿虚线）靠拢。

5. 再看一个例子：卡特兰数

组合学里最出名的数列之一是卡特兰数（Catalan numbers）\(C_n=\dfrac{1}{n+1}\binom{2n}{n}\)。它数的是合法括号串、二叉树等许多对象的个数。用刚得到的中心二项式系数的多项式精度，立刻能写出卡特兰数的多项式精度：

推演.
  1. 代入：\(C_n=\dfrac{1}{n+1}\binom{2n}{n}\sim\dfrac{1}{n+1}\cdot\dfrac{4^n}{\sqrt{\pi n}}\)。
  2. 当 \(n\to\infty\) 时 \(n+1\sim n\)，所以 \(\dfrac{1}{(n+1)\sqrt{\pi n}}\sim\dfrac{1}{n\sqrt{\pi n}}=\dfrac{1}{\sqrt{\pi}\,n^{3/2}}\)。
  3. 因此 \[C_n\;\sim\;\frac{4^{n}}{\sqrt{\pi}\,n^{3/2}}.\] ♦
对照 两者的指数底数都是 \(4\)——单凭指数精度根本分不开它们；但它们的多项式因子不同（\(n^{-1/2}\) 对 \(n^{-3/2}\)）。这正说明：多项式精度能区分指数精度看起来“一模一样”的两个数列。
指数精度只看到 “底数 4”，两条线被压成同一个标签 4ⁿ·n⁻¹ᐟ² 4ⁿ·n⁻³ᐟ² 多项式因子 把二者区分开
同样的指数底数 \(4\)，但 \(\binom{2n}{n}\)（蓝）与 \(C_n\)（红）的多项式因子相差一个 \(n^{-1}\)。多项式精度看得见这个差别，指数精度看不见。
即时自测
  1. 用斯特林公式说明 \(n!\) 的指数增长率为何不存在有限值（即 \((n!)^{1/n}\to\infty\)），并求出 \(\left(\dfrac{n^n}{n!}\right)^{1/n}\) 的极限。
  2. 已知 \(\binom{2n}{n}\sim\dfrac{4^n}{\sqrt{\pi n}}\)。请写出 \(\dfrac14\binom{2n}{n}\) 的多项式精度形式，并说明它的指数底数与多项式因子各是什么。
  3. 设两个数列分别满足 \(a_n\sim 3^n\cdot n^2\) 与 \(b_n\sim 3^n\cdot n^{-2}\)。它们的指数增长率相同吗？它们的多项式因子分别是什么？为什么仅靠 \(a_n^{1/n},\,b_n^{1/n}\) 无法区分二者？

返回 全书目录