阶乘与中心系数的渐近

线性近似处理的是 $x \to 0$：把 $(1+x)^n$ 的高次项丢掉，误差随 $x$ 的幂衰减。本页处理另一端 $n \to \infty$：阶乘与组合数本身没有初等闭式可以化简，但它们的量级有。Stirling 公式（Stirling's approximation）把 $n!$ 写成一个初等表达式，误差随 $n$ 增大而收缩；代进 $C(2n, n)$ 就得到中心二项式系数的量级，而这正是判断一个指数级算法有多大的常用工具。

1 · Stirling 公式的相对误差

记号 $\sim$ 指两边之比趋于 $1$，不是两边之差趋于 $0$——$n = 100$ 时两者的差已有 $10^{154}$ 量级，比值却只差万分之一。更精确的展开给出 $n! = \sqrt{2\pi n}\,(n/e)^n \left(1 + \frac{1}{12n} + \frac{1}{288n^2} + \cdots\right)$，括号里的修正项恒为正，近似值因此恒小于精确值，相对误差的主项是 $1/(12n)$。

逐 $n$ 实测（logFactorial 与 logStirling 在对数域相减，再取 $1 - e^{\Delta}$）：

最右一列从下方单调逼近 $1$，$n$ 扫到 $500$ 仍未越过（$n = 500$ 处为 $0.99992$）。值得记住的是第一行：$n = 1$ 时公式给出 $0.9221$ 而非 $1$，只差 $7.8\%$——一个只在 $n \to \infty$ 时才被声明成立的近似，在最小的那个 $n$ 上已经准到两位有效数字。

2 · 中心二项式系数的量级

把 Stirling 公式代进 $C(2n, n) = (2n)!/(n!)^2$，三步即得：

分子分母的 $n^{2n} e^{-2n}$ 整段抵消，只剩 $4^n$ 与两个根号之商 $\sqrt{4\pi n}/(2\pi n) = 1/\sqrt{\pi n}$。

这个式子给出 Pascal 三角与二项式定理的一条量级结论：第 $2n$ 行全部元素之和是 $4^n$，而其中最大的一项只占 $1/\sqrt{\pi n}$。行越往下越平，没有哪一项能占住常数比例——$n = 100$ 时最大项占全行的 $5.63\%$，$n = 5000$ 时只剩 $0.798\%$。图 1-1 的第二档给出这两条曲线的贴合程度：比值在 $n = 50$ 时为 $0.99750$，$n = 5000$ 时为 $0.999975$，缺口的主项是 $1/(8n)$，实测偏差在 $1/(64n^2)$ 之内。

3 · 复杂度里的量级排序

$2^n$、$C(n, n/2)$ 与 $n!$ 三者的排序靠的就是这类估计。$n$ 为偶数时 $C(n, n/2) \sim 2^n \sqrt{2/(\pi n)}$：枚举「恰好一半」的子集比枚举全部子集只小一个 $\sqrt{n}$ 因子，二者是同一量级的指数，把算法从前者改成后者不会换来实质加速。$n!$ 则完全不同，取对数得 $\ln n! \sim n \ln n - n$，比 $2^n$ 的 $n \ln 2$ 高出一个 $\ln n$ 因子。

Catalan 数可以顺着同一条路算：$C_n = C(2n, n)/(n+1)$，除掉的 $n+1$ 直接落到渐近式上，

比中心系数多掉一个 $n$ 的因子。这条式子收敛得比 $C(2n, n)$ 慢：实测 $n = 100$ 时比值才 $0.9889$，$n = 1000$ 时 $0.9989$，因为 $n+1$ 与 $n$ 之差本身就是 $O(1/n)$ 的相对偏差。

4 · 对数域的计算路线

一个更隐蔽的坑出在 $C(2n, n)/4^n$ 上。这个比值恒小于 $1$，按定义直算却先于分母崩掉：comb(2n, n) 在 $n = 511$ 已是 Infinity，而 $4^n$ 撑到 $n = 512$ 才溢出，$n = 511$ 处算出的是 Infinity 而非真值 $0.0250$。本页的 centralRatio 因此写成 $\exp(\ln (2n)! - 2 \ln n! - 2n \ln 2)$，$n = 5000$ 照样有值。

两条路线各有适用面：要精确整数就走大整数与素因子分解（见组合数的计算），要量级与比例就走本页的渐近式与对数。对数路线的另一处代价在精度。Math.exp(logFactorial(170)) 给出 7.257415615309707e+306，朴素累乘 fact(170) 给出 7.257415615307994e+306，两者从第 12 位有效数字起分家，那是 $170$ 次 Math.log 与一次 Math.exp 攒下的舍入。

5 · 参考文献

1. Stirling's approximation. Wikipedia. Stirling 公式的多种推导、误差界与 $1/(12n)$ 修正项。https://en.wikipedia.org/wiki/Stirling%27s_approximation
2. Central binomial coefficient. Wikipedia. $C(2n, n)$ 的性质、渐近式与相关恒等式。https://en.wikipedia.org/wiki/Central_binomial_coefficient
3. Catalan number. Wikipedia. Catalan 数的定义、组合解释与 $4^n n^{-3/2}\pi^{-1/2}$ 渐近。https://en.wikipedia.org/wiki/Catalan_number