組合學與計數方法

巴斯卡三角形與巴斯卡法則

/ pas-KAL /

在最上方寫一個 1。下面每一新列都以 1 開頭、以 1 結尾,而每個內部數字都是它正上方兩數之和。於是得到一個逐漸長大的三角形:1;接著 1 1;接著 1 2 1;接著 1 3 3 1;接著 1 4 6 4 1,如此永遠下去。這就是巴斯卡三角形,它整齊的算術背後藏著整個二項式係數家族。

這些數字不只是好看——第 n 列、第 k 個位置(從 0 數起)的數恰好是 C(n,k)。所以第 4 列讀作 1 4 6 4 1,就是 C(4,0)、C(4,1)、C(4,2)、C(4,3)、C(4,4)。「把上方兩數相加」這個構造其實是一個喬裝過的定理,叫巴斯卡法則:C(n,k) = C(n-1, k-1) + C(n-1, k)。用純計數說明它為何成立:要從 n 個中挑 k 個,盯住某一個特定的東西;要嘛把它選入(則從其餘 n-1 個中再挑 k-1 個,得 C(n-1,k-1)),要嘛把它排除(則從其餘 n-1 個中挑全部 k 個,得 C(n-1,k))。這兩種互斥情況相加——又是加法原理。

巴斯卡法則是不用階乘、只靠相加就能建出二項式係數的實用辦法。三角形也以左右鏡像對稱展現了 C(n,k) = C(n,n-k),而每一列的和是 2^n。同樣的陣列早在數百年前就出現在中國數學中,稱為楊輝三角,而它悄悄地編碼了二項式定理,因為第 n 列正是 (a+b)^n 的各項係數。

要從第 4 列(1 4 6 4 1)得到第 5 列,把相鄰兩數相加:1、(1+4)=5、(4+6)=10、(6+4)=10、(4+1)=5、1,得到 1 5 10 10 5 1。用公式檢驗:C(5,2) = 10。總和 1+5+10+10+5+1 = 32 = 2^5。

每個項都是 C(n,k);巴斯卡法則 C(n,k)=C(n-1,k-1)+C(n-1,k) 構造出三角形。

注意編號:列與位置通常從 0 數起,所以最上方那個 1 是第 0 列,而第 n 列的第二個項是 C(n,1) = n,不是 C(n,0)。

又稱
Pascal trianglePascal's identityaddition formula for binomial coefficients巴斯卡三角楊輝三角巴斯卡恆等式