深度长文ArticleSep 7, 20261 分钟 min read

从杨辉三角到千万级大数：组合数 C(n, r) 与阶乘的高效防溢出计算

拆解组合数 C(n, r) 与排列数 P(n, r) 的数学模型与计算陷阱：阶乘爆炸为何让朴素公式在 n=21 时直接溢出、杨辉三角加法递推与乘除交替约分算法的优劣对比，以及如何用 BigInt 在浏览器端实现零损耗的大数精确组合计数。

在离散数学、概率论与算法竞赛中，排列（Permutations, $nPr$ ） 与 组合（Combinations, $nCr$ ） 是最基础的计数模型。

初学者在教科书上学到的组合公式极为优雅：

C(n, r) = \binom{n}{r} = \frac{n!}{r! (n - r)!}

很多初学者顺着这个思路，第一反应是写一个递归或循环的 factorial(n) 函数，分别算出分子 $n!$ 和分母两个阶乘，然后相除得到结果。

但在计算机世界里，这种直觉写法堪称“教科书式的反模式”：阶乘函数的爆炸速度远超所有多项式甚至大多数指数函数。即便最终的组合数小到可以用普通整数装下（例如 $C(60, 30)$ ），分子的阶乘 $60!$ 却早在半途就已经把计算机的寄存器炸穿了。

本站的组合与排列计算器支持大数精确无溢出计算。这篇文章详细拆解阶乘爆炸的物理边界，以及如何通过数学结构实现零溢出、高效率的大数组合计数。

1. 阶乘爆炸的残酷账本

要理解为什么朴素公式不可行，首先看一组阶乘在计算机二进制下的真实尺寸账：

$10! = 3,628,800$ （约 362 万，普通的 32 位整型轻松存放）；
$12! = 479,001,600$ （32 位有符号整型的极限为 $2^{31}-1 \approx 2.14 \times 10^9$ ，因此 $13!$ 直接打穿 32 位整型）；
$20! \approx 2.43 \times 10^{18}$ （标准 64 位无符号整型上限为 $2^{64}-1 \approx 1.84 \times 10^{19}$ ，因此 $21!$ 直接打穿 64 位整型）；
$170! \approx 7.25 \times 10^{306}$ （JavaScript 64 位双精度浮点数的上限约为 $1.79 \times 10^{308}$ ， $171!$ 直接溢出为 Infinity）。

假设我们要计算从 60 件物品中挑选 30 件的组合数：

最终答案： $C(60, 30) = 118,264,581,564,861,424$ （约 $1.18 \times 10^{17}$ ）。这个数字虽能放入 64 位有符号整数（上限约 $9.22 \times 10^{18}$ ），但已经显著超出了 JavaScript 原生双精度浮点数 Number.MAX_SAFE_INTEGER（ $2^{53} - 1 \approx 9.007 \times 10^{15}$ ），这也是为什么现代 Web 端必须引入 BigInt 才能无损存储的原因；
但如果按照定义先算分子 $60! \approx 8.32 \times 10^{81}$ ：在 64 位整数体系下它早就溢出了不知道多少轮；就算用浮点数硬算，也会丢失大部分低位有效数字，最终除出来的结果漏洞百出。

先乘到极大值再除以极大值，是数值计算中的大忌。

为了优雅且精确地算出组合数，计算机科学家发展出了四种不同的算法体系：

利用杨辉三角的组合恒等式：

\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}

优点：整个计算过程纯粹只有加法，绝无任何除法和乘法，永远不需要担心整除或约分问题；
缺点：时间复杂度和空间复杂度均为 $O(n \times r)$ 。如果需要计算 $C(10000, 50)$ ，需要维护巨大的二维数组，在 Web 端会消耗大量内存与时间。

根据约分，分子分母的 $(n - r)!$ 可以直接约掉：

C(n, r) = \frac{n \times (n - 1) \times \dots \times (n - r + 1)}{1 \times 2 \times \dots \times r}

一个关键的数论定理保证：任意连续 $k$ 个正整数的乘积，必定能被 $k!$ 整除。

因此，我们可以从 $i = 1$ 到 $r$ 边乘边除：

let res = 1n;
for (let i = 1n; i <= r; i++) {
    res = (res * (n - r + i)) / i;
}

在每一次循环中，分子正好累积了 $i$ 个连续整数的乘积，因此它必定能被当前的 $i$ 整除（余数必定为 0）。这种算法每一步都立刻将数字除小，极大地延缓了中间结果的膨胀，且只需 $O(r)$ 步。

根据组合的对称性：从 $n$ 个元素中选出 $r$ 个，等价于选出要舍弃的 $n - r$ 个：

C(n, r) = C(n, n - r)

在进入循环前，只需执行一行剪枝：

r \leftarrow \min(r, n - r)

如果要计算 $C(100, 98)$ ，瞬间化简为 $C(100, 2)$ ，计算步数从 98 步直接骤降为 2 步！

在现代 JavaScript（ES2020+）中，引入了原生的任意精度整型 BigInt。配合对称性剪枝与乘除交替算法，即便用户输入 $C(1000, 50)$ ，中间结果即便膨胀到数百位，BigInt 也能毫发无损地以微秒级速度完成精确计算，彻底杜绝浮点数截断导致的“末位失真”。

在工程实现中，我们将这套防溢出思想统一整合为三个互相关联的离散数学核心函数：

组合数 $nCr$ ：采用对称性剪枝 + 乘除交替 + BigInt；
排列数 $nPr$ ： $P(n, r) = n \times (n - 1) \times \dots \times (n - r + 1)$ 直接以 BigInt 连乘 $r$ 个项，无需除法；
全排列与阶乘 $n!$ ： $n! = P(n, n)$ 在输入框中设置安全界限（例如限制 $n \le 10000$ ，避免瞬间构造出占用数兆内存的怪物大数）。

这种将数论性质（连续整数整除定理）与现代语言原生大数特性深度结合的架构，正是保证浏览器端科学工具又轻、又快、又绝对精确的基石。