组合数的一种快速算法

在解决一些数学问题时，我们可能会用到组合数的计算，本文介绍一种计算组合数的快速和安全的方法。

最基本的，组合数的数学计算公式为： $$C_{m}^{n}=\frac{m!}{n!(m-n)!}$$ 那么，最基础的思路即为分别计算出分子分母中的三个阶乘，进一步计算出组合数。这种思路的问题显而易见：阶乘的增长率太大。64 位无符号整数的最大值为 $18,446,744,073,709,551,615$，而 $21!=51,090,942,171,709,440,000$，已经超过了前者，更不要说分母还要相乘了。

容易想到，我们可以参考人类手算组合式的模式来减少不必要的计算： $$\begin{align} C_{m}^{n}&=\frac{m!}{n!(m-n)!} \newline &=\frac{1\times2\times3\times…\times(m-1)\times m}{1\times2\times3\times…\times(n-1)\times n \times 1\times2\times3\times…\times(m-n-1)\times(m-n)} \newline &=\frac{(n+1)\times(n+2)\times…\times(m-1)\times m}{1\times2\times3\times…\times(m-n-1)\times(m-n)} \end{align}$$ 可以观察一下上面的结果。分子共有 $m-(n+1)+1=m-n$ 项，分母也有 $m-n$ 项，我们把上式改写成： $$\begin{align} C_{m}^{n}&=\frac{(n+1)\times(n+2)\times…\times(m-1)\times m}{1\times2\times3\times…\times(m-n-1)\times(m-n)} \newline &=\frac{n+1}{1}\times\frac{n+2}{2}\times…\times\frac{m-1}{m-(n+1)}\times\frac{m}{m-n} \end{align}$$ 容易看出来，对于每一项，分子总是分母加 $n$，且分母的范围为 $[1,m-n]$。

基于以上结论，我们容易写出代码：

function combination(m: number, n: number): number
{
    // ...省略错误检查代码...
    let result = 1;
    for (let i = 1; i <= m - n; i++)
    {
        // 先做除法再做乘法，避免溢出
        result /= i;
        result *= i + n;
    }
    return result;
}