杨辉三角的5个特性，一个比一个牛皮！

作者：小傅哥
博客：https://bugstack.cn

沉淀、分享、成长，让自己和他人都能有所收获！??

一、前言

杨辉三角的历史

杨辉三角按照杨辉于1261年所编写的《详解九章算法》一书，里面有一张图片，介绍此种算法来自于另外一个数学家贾宪所编写的《释锁算书》一书，但这本书早已失传无从考证。但可以肯定的是这一图形的发现我国不迟于1200年左右。在欧洲，这图形称为"巴斯加(Pascal)三角"。因为一般都认为这是巴斯加在1654年发明的。其实在巴斯加之前已经有许多人普及过，最早是德国人阿匹纳斯(Pertrus APianus)，他曾经把这个图形刻在1527年著的一本算术书封面上。但无论如何，杨辉三角的发现，在我国比在欧洲至少要早300年光景。

此外杨辉三角原来的名字也不是三角，而是叫做开方作法本源，后来也有人称为乘法求廉图。因为这些名称实在太古奥了些，所以后来简称为“三角”。

在小傅哥学习杨辉三角的过程中，找到了一本大数学家华罗庚的PDF《程序员数学：斐波那契》—— 为什么不能用斐波那契散列，做数据库路由算法？

斐波那契数列可以由递归关系定义：F0 = 0，F1 = 1，Fn = Fn-1 + Fn-2

而这样一个有规律的斐波那契数列在杨辉三角中也是有所体现的。

• 把斜对角的数字做加和，会得到一组斐波那契数列；1、1、2、3、5、8、13、15、33

4. 次方数

在杨辉三角中还有一个非常有意思的特性，就是有2的次方和11次方数。

2次方

11次方

• 另外一个是11的次幂，例如11的2次幂的结果正好是121这一排数字的组合。如果是11的5次幂，中间有连续的10，则是把后一位向前一位进位一下。

5. 平方数

• 在杨辉三角中还有一个平方数的规律体现。比如3的平方正好是右侧3+6的结果。4的平方是右侧6+10的结果。

四、杨辉三角实现

接下来我们实现下杨辉三角；

public HashMap pascalTriangle(int lineNumber) {
    HashMap currentLine = new HashMap<>();
    currentLine.put(0, 1);
    int currentLineSize = lineNumber + 1;
    for (int numberIdx = 1; numberIdx < currentLineSize; numberIdx += 1) {
        /*
         * https://github.com/trekhleb/javascript-algorithms/blob/master/src/algorithms/math/pascal-triangle/pascalTriangle.js
         * 第i行号中的第 -th 个条目lineNumber是 Binomial CoefficientC(lineNumber, i)并且所有行都以 value 开头1。这个思路是C(lineNumber, i)使用C(lineNumber, i-1). 它可以O(1)使用以下方法及时计算：
         * C(lineNumber, i)   = lineNumber! / ((lineNumber - i)! * i!)
         * C(lineNumber, i - 1) = lineNumber! / ((lineNumber - i + 1)! * (i - 1)!)
         *
         * 从以上两个表达式我们可以推导出下面的表达式：C(lineNumber, i) = C(lineNumber, i - 1) * (lineNumber - i + 1) / i
         * 所以C(lineNumber, i)可以从C(lineNumber, i - 1)时间上算出来O(1)
         */
        currentLine.put(numberIdx, ((null == currentLine.get(numberIdx - 1) ? 0 : currentLine.get(numberIdx - 1)) * (lineNumber - numberIdx + 1)) / numberIdx);
    }
    return currentLine;
}

单元测试

@Test
public void test_PascalTriangle() {
    PascalTriangle pascalTriangle = new PascalTriangle();
    for (int i = 0; i <= 10; i++) {
        HashMap currentLineMap = pascalTriangle.pascalTriangle(i);
        System.out.println(JSON.toJSONString(currentLineMap.values()));
    }
}

[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
[1,6,15,20,15,6,1]
[1,7,21,35,35,21,7,1]
[1,8,28,56,70,56,28,8,1]
[1,9,36,84,126,126,84,36,9,1]
[1,10,45,120,210,252,210,120,45,10,1]

• 这样我们可以得到一组杨辉三角数列了。

五、常见面试题

• 杨辉三角有哪些用途？
• 用代码实现下杨辉三角。—— 在LeetCode中也有这样的题目