一、前言

楊輝三角的歷史

楊輝三角按照楊輝于1261年所編寫的《詳解九章算法》一書，里面有一張圖片，介紹此種算法來自于另外一個數(shù)學家賈憲所編寫的《釋鎖算書》一書，但這本書早已失傳無從考證。但可以肯定的是這一圖形的發(fā)現(xiàn)我國不遲于1200年左右。在歐洲，這圖形稱為"巴斯加(Pascal)三角"。因為一般都認為這是巴斯加在1654年發(fā)明的。其實在巴斯加之前已經(jīng)有許多人普及過，最早是德國人阿匹納斯(Pertrus APianus)，他曾經(jīng)把這個圖形刻在1527年著的一本算術(shù)書封面上。但無論如何，楊輝三角的發(fā)現(xiàn)，在我國比在歐洲至少要早300年光景。

此外楊輝三角原來的名字也不是三角，而是叫做開方作法本源，后來也有人稱為乘法求廉圖。因為這些名稱實在太古奧了些，所以后來簡稱為“三角”。

在小傅哥學習楊輝三角的過程中，找到了一本大數(shù)學家華羅庚的PDF《從楊輝三角談起 - 華羅庚》?！?這些數(shù)學真的非常重要，每每映射到程序中都是一段把for循環(huán)優(yōu)化成算法的體現(xiàn)，提高執(zhí)行效率。

二、楊輝三角構(gòu)造

在開始分享楊輝三角的特性和代碼實現(xiàn)前，我們先來了解下楊輝三角的結(jié)構(gòu)構(gòu)造。

楊輝三角的結(jié)構(gòu)和規(guī)律非常簡單，除去每次兩邊的1，中間的數(shù)字都是上面兩個數(shù)字的和。如圖示意的三角區(qū)域。但也就是如此簡單的結(jié)構(gòu)，卻有著諸多的數(shù)學邏輯體現(xiàn)。包括我們計算的二項式、N選X的種數(shù)還有斐波那契數(shù)列等，都可以在楊輝三角中體現(xiàn)出來。接下來我們就來看看這些特性。

三、楊輝三角特性

為了方便學習楊輝三角的數(shù)學邏輯特性，我們把它按左對齊方式進行排列。

[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]

接下來我們就以這組楊輝三角數(shù)列，來展示它的數(shù)學邏輯特性。關于楊輝三角的Java代碼放已到下文中，讀者可以查閱。

1. 二項式展開

大家在上學階段一定學習過二項式展開，例如：(x+y)^2 = x^2 + 2xy + y^2 其實這個展開的數(shù)學邏輯在楊輝三角中可以非常好的展示出來。

• 任意一個二項式展開后的數(shù)字乘積，都可以映射到楊輝三角對應的中的數(shù)字。
• 二項式展開公式是用來計算給定二項式的指數(shù)冪的展開式的公式。對于給定的二項式 (x + y)n，二項式展開公式為：(x + y)^n = x^n + nx^{n-1}y + n(n-1)x^{n-2}y^2 + ... + y^n這個公式也正好符合楊輝三角的數(shù)字值。

2. 組合數(shù)

組合數(shù)是數(shù)學中定義的一種數(shù)學概念，用于計算有多少種選擇可以從一組物品中選擇出若干的物品。比如你早上有5種水果可以吃，但你吃不了那么多，讓你5種水果中選2個，看看有多少種選擇。通過使用公式 c(n,k) = n!/k!(n-k)! 可以計算出，5選2有10種選擇。

那么這樣一個計算也是可以體現(xiàn)在楊輝三角中的。

• 5選2，在楊輝三角中可以找到第5行的第2列，結(jié)果是10。按照這個規(guī)律，5選3=10、5選4=5

3. 斐波那契數(shù)列

斐波那契數(shù)列出現(xiàn)在印度數(shù)學中，與梵文韻律有關。在梵語詩歌傳統(tǒng)中，人們對列舉所有持續(xù)時間為 2 單位的長 (L) 音節(jié)與 1 單位持續(xù)時間的短 (S) 音節(jié)并列的模式很感興趣。關于更多斐波那契更多知識可以閱讀小傅哥的：《程序員數(shù)學：斐波那契》—— 為什么不能用斐波那契散列，做數(shù)據(jù)庫路由算法？

斐波那契數(shù)列可以由遞歸關系定義：F0 = 0，F(xiàn)1 = 1，F(xiàn)n = Fn-1 + Fn-2

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 0 1 1 2 3 5 8 13 21 34

而這樣一個有規(guī)律的斐波那契數(shù)列在楊輝三角中也是有所體現(xiàn)的。

• 把斜對角的數(shù)字做加和，會得到一組斐波那契數(shù)列；1、1、2、3、5、8、13、15、33

4. 次方數(shù)

在楊輝三角中還有一個非常有意思的特性，就是有2的次方和11次方數(shù)。

2次方

- 楊輝三角每一行的數(shù)字加和，正好的2的0次方、1次方..n次方

11次方

• 另外一個是11的次冪，例如11的2次冪的結(jié)果正好是121這一排數(shù)字的組合。如果是11的5次冪，中間有連續(xù)的10，則是把后一位向前一位進位一下。

5. 平方數(shù)

• 在楊輝三角中還有一個平方數(shù)的規(guī)律體現(xiàn)。比如3的平方正好是右側(cè)3+6的結(jié)果。4的平方是右側(cè)6+10的結(jié)果。

四、楊輝三角實現(xiàn)

接下來我們實現(xiàn)下楊輝三角；

public HashMap<Integer, Integer> pascalTriangle(int lineNumber) {
    HashMap<Integer, Integer> currentLine = new HashMap<>();
    currentLine.put(0, 1);
    int currentLineSize = lineNumber + 1;
    for (int numberIdx = 1; numberIdx < currentLineSize; numberIdx += 1) {
        /*
         * https://git***.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<Integer, Integer> 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]

• 這樣我們可以得到一組楊輝三角數(shù)列了。

五、常見面試題

• 楊輝三角有哪些用途？
• 用代碼實現(xiàn)下楊輝三角?！?在LeetCode中也有這樣的題目?