警告：理解本博文要求有一定的数学功底

0x00 背景

杨辉三角是一个历史非常悠久（接近 1000 年前发现\(^{[1]}\)）的数学概念，其直观表示为：

1
2
3
4
5
6
7
8
9
10
11
          1
         / \
        1   1
       / \ / \
      1   2   1
     / \ / \ / \
    1   3   3   1
   / \ / \ / \ / \
  1   4   6   4   1
 / \ / \ / \ / \ / \
1   5   10  10  5   1

从第三行开始，行内每个数都是其上一层最靠近它的两个数之和。

考虑这个性质，网络上大部分算法都是递推法也就很容易理解了：

1
2
3
4
5
6
7
def triangles():
    L = [1]
    while 1:
        yield L
        L = [1] +  # 行首的1
            [ L[i] + L[i+1] for i in range(len(L) - 1) ] +  # 行中间的数
            [1]  # 行尾的1

但是，身为一名帝都高中生，我们怎么能止步于此呢？如果我只想要杨辉三角第 \(m​\) 行的第 \(n​\) 个数，岂不是还得从第1行一路算下来？这太粗糙了！

所以我们另辟蹊径。

0x01 数学知识

0x01.1 组合数

这很小学奥数

从三个学生里选出两个，共有几种选法？（换一种思路，也可以理解为：从三个学生里扔掉一个，共有几种扔法？）

答案：3 种（选AB，选BC，选AC）

于是我们可以简单地给这种选人问题一个通解：

题目：从 \(m\) 个人里选 \(n\) 个，共有几种选法？

解：先选一个，共 \(m\) 种。再选第二个，共 \(m-1\) 种。……最后选第 \(n\) 个，共 \(m-n+1\) 种。

所以，这时候得到了 \(m\times\cdots\times(m-n+1)\) 也就是 \(\frac{m!}{(m-n+1)!}\) 种选法。然而，注意到先选 A、再选 B，和先选 B、再选 A是同一种，所以之前的结果有重复。

重复了多少次呢？

简单的例子：对于A，B，C，共有6种（ABC，ACB，BAC，BCA，CAB，CBA）。

观察一下，发现这本质上是：先选一个，共 3 种；再选第二个，共 2 种；选最后一个，共 1 种。

也就是说，对于选出来了 \(n\) 个人的情况，应该把之前的结果再除以 \(n\times(n-1)\times\cdots\times1\)，也即 \(n!\)。

最终得到结果：共有 \(\frac{m!}{(m-n+1)!\times n!}​\) 种选法。

定义符号 \(C_m^{\,n}\)，其含义为从 \(m\) 个东西里选出 \(n\) 个的选法，其值为 \(\frac{m!}{(m-n+1)!\times n!}\)。

稍作计算即可得到 \(C_m^{\,n}=C_m^{m-n}​\)。

0x01.2 二项式展开

考虑算式 \((a+b)^n\)，易发现其可以展开为： \[ (a+b)\cdot(a+b)\cdots(a+b) \] （共 \(n\) 个 \((a+b)\)）

于是对其再次进行展开： \[ k_0 a^n+k_1 a^{n-1}b + \cdots +k_n b^n \] 考虑中间某一项 \(k_x a^{n-x}b^x\)，易得知其是 \(n\) 个 \((a+b)\) 相乘时，取出了 \(n-x\) 个括号中的 \(a\) 与剩下的括号里的 \(b\) 相乘，并将系数相加得到的。（狭义二项式定理\(^{[2]}\)）

所以，\(k_x = C_n^x\)。

所以，\((a+b)^n=\sum_{i=0}^n C_n^i\times a^{n-i}b^i​\)。

0x02 实现

杨辉三角中第 \(m+1\) 行的所有 \(n\) 个数的本质其实就是 \((a+b)^m\) 展开后的 \(n\) 个系数。

例如，\((a+b)^2 = a^2+2ab+b^2\)，系数为 \(1,2,1\)，正是杨辉三角的第 3 行。

所以，可以实现任意计算杨辉三角的第 \(m​\) 行的第 \(n​\) 个数了：

\({\rm Yang}(m,n)=C_{m-1}^{\,n-1}\)

That's it!

最终的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"use strict";

/**
 * @description C^m_n
 * @param {Number} n
 * @param {Number} m
 */
function C(n, m) {
    if(m * 2 > n) {
        m = n - m;
    }
    let res = 1;
    for(let i = n; i > n - m; i--) {
        res *= i;
    }
    for(let i = m; i > 0; i--) {
        res /= i;
    }
    return Math.round(res);  // fix IEEE754 Double's precision lost
}

const MAX_LINE = Number(process.argv[2]);

for(let i = 0; i <= MAX_LINE; i++) {
    for(let j = 0; j <= i; j++) {
        process.stdout.write(C(i, j) + " ");
    }
    process.stdout.write("\n");
}

稍作分析即可看出，这种方法只是在计算“第 \(m\) 行的第 \(n​\) 个数”时较快，在整个输出杨辉三角时由于存在大量的重复计算导致其整体的时间复杂度是远高于递推法的。

\([1]\): 百度百科\(.\) 杨辉三角

\([2]\): 百度百科\(.\) 二项式定理

来源：https://blog.jiejiss.com/