巴斯卡三角形

November 29, 2021

巴斯卡(Pascal)三角形的最上面是 1,每列左右兩端也都是 1,第二列起各行相鄰兩數字相加,就是下一列兩數間的數字。例如:

                                 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
1    11    55   165   330   462   462   330   165    55    11     1

若要求第 n 列的數字,該怎麼求呢?

解法思路

巴斯卡三角形與 (x + 1)ⁿ 多項式展開後的係數有關係,來觀察一下:
(x + 1)¹ = x + 1
(x + 1)² = x² + 2x + 1
(x + 1)³ = x³ + 3x² + 3x + 1
(x + 1)⁴ = x⁴ + 4x³ + 6x² + 4x + 1
巴斯卡三角形第 n + 1 列的數字,就是 (x + 1)ⁿ 的多項式展開後降冪排列後的係數。若巴斯卡三角形的每一個數字各對應一個 ᵣCₙ,可以使用以下公式計算,以避免階乘運算時的數值溢位:
ᵣC₀ = 1
ᵣCₙ = rCₙ₋₁ * (r - n + 1) / n

實作上可以採用遞迴:

Procedure COMBI(R, N) 
    IF (N = 0) 
        RETURN 1
    ELSE 
        RETURN COMBI(R, N - 1) * (R - N + 1) / N 

或者使用迴圈:

Procedure COMBI(R, N) 
    FOR(i = 1; i <= N; i = i + 1)
        p = p * (R - i + 1) / i
    RETURN p

巴斯卡三角形有個與質數相關的特性,(x + 1)ⁿ 的多項式展開後降冪排列後的係數,除了 xⁿ 與 1 以外的係數,若可以被 n 整除,n 就是質數,你可以自行驗證看看。

程式實作

#include <stdio.h>
#define HEIGHT 12

int combi(int r, int n){
    int p = 1;
    int i;
    for(i = 1; i <= n; i++) {
        p = p * (r - i + 1) / i;
    }
    return p;
}

int main() {
    int r;
    for(r = 0; r < HEIGHT; r++) {
        char format[5];            
        sprintf(format, "%%%ds", (HEIGHT - r) * 3);
        printf(format, "");
        int n;
        for(n = 0; n <= r; n++) {
            printf("%6d", combi(r, n));
        }
        printf("\n");
    }
    return 0;
} 
import static java.lang.System.out;
import java.util.*;

public class Pascal {
    private List<List<Integer>> rows = new ArrayList<>();
    
    Pascal(int height) {
        for(int r = 0; r < height; r++) {
            rows.add(createRow(r));
        }
    }
    
    int combi(int r, int n) {
        return rows.get(r).get(n);
    }
    
    private List<Integer> createRow(int r){
        List<Integer> row = new ArrayList<>();
        row.add(1);
        for(int n = 1; n <= r; n++) {
            row.add(row.get(n - 1) * (r - n + 1) / n);
        }
        return row;
    }
    
    public static void main(String[] args) {
        final int HEIGHT = 12;
        Pascal p = new Pascal(HEIGHT);
        for(int r = 0; r < HEIGHT; r++) {
            out.printf(String.format("%%%ds", (HEIGHT - r) * 3), "");
            for(int n = 0; n <= r; n++) {
                out.printf("%6d", p.combi(r, n));
            }
            out.println();
        }
    }
}
def combi(r, n):
    return 1 if n == 0 else combi(r, n - 1) * (r - n + 1) // n
	
height = 12
c = [[combi(r, n) for n in range(r + 1)] for r in range(height)]
 
for r in range(len(c)):
    print(("%" + str((len(c) - r) * 3) + "s") % "", end = "")
    for n in range(len(c[r])):
	    print("%6d" % c[r][n], end = "");
    print()
def combi(r: Int, n: Int): Int = n match {
    case 0 => 1
    case _ => combi(r, n - 1) * (r - n + 1) / n
}

val height = 12
val c = for(r <- 0 until height) yield for(n <- 0 to r) yield combi(r, n)

(0 until c.length).foreach(r => {
    printf("%%%ds".format((c.length - r) * 3), "")
    c(r).foreach(printf("%6d", _))
    println
})
def combi(r, n)
    return 1 if n == 0; combi(r, n - 1) * (r - n + 1) / n
end

height = 12
0.upto(height - 1) do |r|
    printf "%" + ((height - r) * 3).to_s + "s", ""
    0.upto(r) do |n|
       printf "%6d", combi(r, n)
    end
    puts
end
function combi(r, n) {
    if(n == 0) return 1;
    else return combi(r, n - 1) * (r - n + 1) / n;
}

var height = 12;
var pascal = '';
for(var r = 0; r < height; r++) {
    pascal += new Array((height - r) * 3).join(' ');
    for(var n = 0; n <=r; n++) {
        var c = combi(r, n);
        pascal += new Array(6 - (c + '').length).join(' ') + c;
    }
    pascal += '\n';
}
print(pascal);
import Control.Monad
import Text.Printf

combi _ 0 = 1
combi r n = combi r (n - 1) * (r - n + 1) `div` n

main = do
    let height = 12
    forM [0..height - 1] (\r -> do
        putStr \$ take ((height - r) * 3) \$ cycle " "
        sequence [printf "%6d" (combi r n) | n <- [0..r]]
        putStrLn "")
combi(_, 0, 1).
combi(ROW, COL, Result) :- NCOL is COL - 1,
                           combi(ROW, NCOL, NR),
                           Result is (NR * (ROW - COL + 1) / COL).

pascal_row(_, 0) :- writef("%d ", [1]).
pascal_row(ROW, COL) :- combi(ROW, COL, Result),
                        writef("%d ", [Result]),
                        NCOL is COL - 1,
                        pascal_row(ROW, NCOL).

pascal(0) :- pascal_row(_, 0).
pascal(ROWS) :- pascal_row(ROWS, ROWS),
                nl,
                NROWS is ROWS - 1,
                pascal(NROWS).
  
main([Arg0|_]) :-
        atom_number(Arg0, N),
        pascal(N).
# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

def combi(r, n) {
    if n == 0 {
        return 1
    }
    return combi(r, n - 1) * (r - n + 1) / n
}

def space(n) {
    return List.create(n, '').join(' ')
}

HEIGHT = 12

def printRow(row) {
    def printNumber(n) {
        c = combi(row, n) + ''
        print(c + space(6 - c.length()))
    }

    print(space((HEIGHT- row) * 3)) # indentation
    iterate(0, row + 1).forEach(printNumber)
    println()
}

iterate(0, HEIGHT).forEach(printRow)