二項式係數

(重定向自组合数

數學上,二項式係數二項式定理中各項的係數。一般而言,二項式係數由兩個非負整數為參數決定,寫作 ,定義為 的多項式展開式中,項的係數,因此一定是非負整數。如果將二項式係數 寫成一行,再依照 順序由上往下排列,則構成帕斯卡三角形

二項式係數可排列成帕斯卡三角形

二項式係數常見於各數學領域中,尤其是組合數學。事實上,可以被理解為從個相異元素中取出個元素的方法數,所以 大多讀作「」。二項式係數 的定義可以推廣至複數的情況,而且仍然被稱為二項式係數。

歷史及記號

雖然二項式係數在西元10世紀就已經被發現(見帕斯卡三角形),但表達式  卻是到1826年才由安德烈亚斯·冯·厄廷格豪森首次始用[注 1]。最早探討二項式係數的論述是十世紀的 Halayudha英语Halayudha寫的印度教典籍《宾伽罗的計量聖典》(chandaḥśāstra)。約1150年,印度數學家婆什迦羅第二於其著作《Lilavati[注 2] 中給出一個簡單的描述。

二項式係數亦有不同的符號表達方式,包括:     [注 3],其中的 C 代表組合(combinations)或選擇(choices)。很多計算機使用含有 C 的變種記號,使得算式只佔一行的空間,相同理由也發生在置換 ,例如寫作 P(n, k)。

定義及概念

對於非負整数  ,二項式係數 定義為 的多項式展開式中, 項的係數,即

 

事實上,若  交換環上的元素,則

 

此數的另一出處在組合數學,表達了從 物中,不計較次序取 物有多少方式,亦即從一 元素集合中所能組成 元素子集的數量。此定義與上述定義相同,理由如下:若將冪  個因數逐一標記為 (從1至 ),則任一 元素子集則建構成展式中的一個 項,故此該單項的係數等如此種子集的數量。亦因此,就任何自然數  而言, 亦為自然數。此外,二項式係數亦見於很多組合問題的解答中,如由 位元(如數字0或1)組成的所有序列中,其和為 的數目為 ,又如算式 ,其中每一 均為非負整數,則有 種寫法。這些例子中,大部分可視作等同於點算 個元素的組合的數量。

計算二項式係數

除展開二項式或點算組合數量之外,尚有多種方式計算 的值。

遞歸公式

以下遞歸公式可計算二項式係數:

 

其中特別指定:

 
 

此公式可由計算 中的 項,或點算集合  個元素組合中包含 與不包含 的數量得出。

顯然,如果 ,則 。而且對所有  ,故此上述遞歸公式可於此等情況下中斷。遞歸公式可用作建構帕斯卡三角形

乘數公式

個別二項式係數可用以下公式計算:

 

上式中第一個分數的分子是一階乘冪。此公式可以二項式係數在計算組合數量的意義理解:分子為從 個元素中取出 個元素的序列之數量,當中包含同樣的元素但不同排列次序的序列。分母則計算同樣的 個元素可有多少種排序方式。

階乘公式

二項式係數最簡潔的表達式是階乘:

 

其中「 」是 的階乘,此公式從上述乘數公式中分子分母各乘以 取得,所以此公式中的分子分母有眾同共同因子。除非先行抵銷兩邊中的共同因子,否則以此公式進行計算時較率欠佳,尤因階乘的數值增長特快。惟此公式展示了二項式係數的對稱特性:

  1

一般化形式及其與二項式級數的關係

若將 換成任意數值(負數、實數或複數) ,甚至是在任何能為正整數給出逆元素交換環中的一元素,則二項式係數可籍乘數公式擴展[注 4]

 

此定義能使二項式公式一般化(其中一單項為1),故 仍能相稱地稱作二項式係數:

  2

此公式對任何複數   時成立,故此亦可視作 冪級數的恆等式,即係數為常數1,任意冪之級數定義,且在此定義下,對於冪的恆等式成立,例如

 

 是一非負整數 ,則所有 的項為零,此無窮級數變成有限項的和,還原為二項式公式,但對於 的其他值,包括負數和有理數,此級數為無窮級數。

帕斯卡三角形 (楊輝三角)

 
帕斯卡三角形的第1000行,垂直排列,且以灰階表示係數的十進制數位,向右對齊,故左邊邊界約是二項式係數的對數,圖中可見數族形成一對數凹數列

帕斯卡法則是一重要的遞歸等式:

  3

此式可以用於數學歸納法,以証明 對於所有  均為自然數(等同於証明 為所有 個連續整數之積的因數),此特性並不易從公式(1)中得出。

帕斯卡法則建構出帕斯卡三角形:

0: 1
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
5: 1 5 10 10 5 1
6: 1 6 15 20 15 6 1
7: 21 35 35 21
8: 28 56 70 56 28

 橫行列出  項,其建構方法為在外邊填上1,然後將上一行中每兩個相鄰數相加的和填在其下,此方法可快速地計算二項式係數而不涉及乘法或分數,例如從第5橫行可馬上得出

 

在斜線上相鄰項的差就是上一斜線上的數值,此乃上述遞歸等式(3)的延伸意義。

組合數學和統計學

二項式係數是組合數學中的重要課題,因其可用於眾多常見的點算問題中,例如

  • 共有 種方式從 元素中選取 項。見組合
  • 共有 種方式從一個 元素集合中選取(容許重覆選取) 元素建立多重集
  • 共有 字符串包含 個1和 個零。
  • 共有 個字符串包含 個1和 個零,且沒有兩個1相鄰。[参 1]
  • 卡塔蘭數 
  • 統計學中的二項式分佈 
  • 貝茲曲線的公式。

以多項式表達二項式係數

就任就非負整數  可表達為一多項式除以 

 

此為帶有理數係數,變量是 多項式,可對任意實數或複數 運算以得出二項式係數,此「廣義二項式係數」見於牛頓廣義二項式定理

就任意 ,多項式 可看成是惟一的 次多項式 滿足  .

其係數可以第一類斯特靈數表示,即:

 

 導數可以對數微分計算:

 

以二項式係數為多項式空間之基底

在任何包含Q中,最多 階的多項式有惟一的線性組合 。係數 是數列 k差分,亦即: [注 5]

  3.5

整數值多項式

每一多項式 在整數參數時均是整數值(可在 上,用帕斯卡法則以歸納法証明)。故此,二項式係數多項式的整數線性組合亦為整數值。反之,(3.5)表達了任何整數值的多項式均是二項式係數多項式的整數線性組合。一般而言,對於一個特徵0域 的任何子環 ,在 內的多項式在整數參數時之值均在 內當且僅當該多項式是一二項式係數多項式的 -線性組合。

整數值多項式 可表達作:

 

  帕斯卡矩阵可算出:

 
 

这种二項式係數多項式结合朱世杰恒等式应用于等幂求和

有關二項式係數的恆等式

关系式

階乘公式能聯繫相鄰的二項式係數,例如在 是正整數時,對任意 有:

  •  
  •  
  •  

两个组合数相乘可作变换:

 [参 2]

一阶求和公式

  •  
  •  
  •  
  •  [参 3]
  •  
 
  •  [参 4]
 
  •  
 

二阶求和公式

  •  
  •  [参 5]
 
 
 
  •  

三阶求和公式

  •  

備註

  1. ^ Higham (1998)
  2. ^ Lilavati 第6節,第4章(見Knuth (1997))。
  3. ^ Shilov (1977)
  4. ^ 見(Graham, Knuth & Patashnik 1994),其中就 定義了 ,其他一般化形式包括考慮兩參數為實數或複數時以伽瑪函數 時定義 ,但此舉會令大部分二項式係數的恆等式失效,故未有被廣泛採用。然而,此方法替不等於零的參數下定義則可得出如Hilton, Holton and Pedersen, Mathematical reflections: in a room with many mirrors, Springer, 1997中那種好看的「帕斯卡風車」,但是卻會令帕斯卡法則在原點失效。
  5. ^ 此可視作泰勒定理的離散形式,亦與牛頓多項式有關,此式的交錯項之和可以Nörlund–Rice積分表示。

參考文獻

  1. ^ Muir, Thomas. Note on Selected Combinations. Proceedings of the Royal Society of Edinburgh. 1902. 
  2. ^ 两个排列组合求和公式. [2014-01-05]. (原始内容存档于2019-05-02). 
  3. ^ 赵丽棉 黄基廷. n次单位根在代数问题中的应用. 高等数学研究. 2010, (4) [2014-01-24]. (原始内容存档于2019-05-02). 
  4. ^ 徐更生 何廷模. 斐波那契数列与组合数的一个关系及推广. 中学教研. 1991, (10) [2014-01-04]. (原始内容存档于2019-05-02). 
  5. ^ 伍启期. 组合数列求和. 佛山科学技术学院学报(自然科学版). 1996, (4) [2014-05-24]. (原始内容存档于2019-05-02). 

参见

外部連結