二項式係數

维基百科,自由的百科全书
跳转至: 导航搜索
二項式係數可排列成杨辉三角形

二項式係數數學上是二項式定理中的係數族。其必然為正整數,且能以兩個非負整數為參數確定,此兩參數通常以nk代表,並將二項式係數寫作,亦即是二項式(1 + x) n多項式展式中,x k項的係數。如將二項式係數的n值順序排列成行,每行為k值由0至n列出,則構成帕斯卡三角形

此數族亦常見於其他代數學領域中,尤其是組合數學。任何有n個元素的集合,由其衍生出擁有k個元素的子集,即由其中任意k個元素的組合,共有個。故此亦常讀作「n選取k」。二項式係數的特性使表達式的定義不再局限於nk均為非負整數及kn,然此等表達式仍被稱為二項式係數。

雖然此數族早已被發現(見帕斯卡三角形),但表達式則是由安德烈亚斯·冯·厄廷格豪森於1826年始用[注 1]。最早探討二項式係數的論述是十世紀的Halayudha寫的印度教典籍《Pingala的計量聖典》(chandaḥśāstra),及至約1150年,印度數學家Bhaskaracharya於其著作《Lilavati[注 2] 中給出一個簡單的描述。

二項式係數亦有不同的符號表達方式,包括:C(n, k)、nCknCk[注 3],其中的C代表組合(combinations)或選擇(choices)。

定義及概念[编辑]

考慮包含0的自然數nk,則二項式係數定義為(1 + X)n的展式中,單項Xk係數,亦即在二項式定理中的係數

(任何交換環元素xy中有定義),亦因此得名為「二項式係數」。

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

計算二項式係數[编辑]

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

遞歸公式[编辑]

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

其中特別指定:

此公式可由計算(1 + X)n−1(1 + X)中的Xk項,或點算集合{1, 2, ..., n}的k個元素組合中包含n與不包含n的數量得出。

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

乘數公式[编辑]

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

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

階乘公式[编辑]

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

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

   
(1)

   

一般化形式及其與二項式級數的關係[编辑]

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

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

   
(2)

   

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

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

帕斯卡三角形 (楊輝三角)[编辑]

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

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

   
(3)

   

此式可以用於數學歸納法,以証明對於所有nk均為自然數(等同於証明k!為所有k個連續整數之積的因數),此特性並不易從公式(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

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

(x + y)5 = 1 x5 + 5 x4y + 10 x3y2 + 10 x2y3 + 5 x y4 + 1 y5

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

組合數學和統計學[编辑]

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

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

以多項式表達二項式係數[编辑]

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

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

就任意k,多項式可看成是惟一的k次多項式p(t)滿足p(0) = p(1) = ... = p(k − 1) = 0 及 p(k) = 1.

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

導數可以對數微分計算:

以二項式係數為多項式空間之基底[编辑]

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

   
(3.5)

   

整數值多項式[编辑]

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

整數值多項式 3t(3t + 1)/2 可表達作:

从t=1,2,3时 3t(3t + 1)/2 =6,21,45用帕斯卡矩阵可算出:

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

有關二項式係數的恆等式[编辑]

关系式[编辑]

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

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

[参 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. ^ 两个排列组合求和公式. 
  3. ^ 赵丽棉 黄基廷. n次单位根在代数问题中的应用. 高等数学研究. 2010, (4). 
  4. ^ 徐更生 何廷模. 斐波那契数列与组合数的一个关系及推广. 中学教研. 1991, (10). 
  5. ^ 伍启期. 组合数列求和. 佛山科学技术学院学报(自然科学版). 1996, (4). 

外部連結[编辑]

本條目含有来自PlanetMathBinomial Coefficient》的材料,版权遵守乃遵守知识共享协议:署名-相同方式共享协议

本條目含有来自PlanetMathBounds for binomial coefficients》的材料,版权遵守乃遵守知识共享协议:署名-相同方式共享协议

本條目含有来自PlanetMathProof that C(n,k) is an integer》的材料,版权遵守乃遵守知识共享协议:署名-相同方式共享协议

本條目含有来自PlanetMathGeneralized binomial coefficients》的材料,版权遵守乃遵守知识共享协议:署名-相同方式共享协议