跳至內容

二項式系數

維基百科,自由的百科全書
二項式系數可排列成帕斯卡三角形

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

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

歷史及記號

雖然二項式系數在西元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). 

參見

外部連結