二項式係數

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

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

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

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

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

定義及概念[编辑]

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

(x+y)^n=\sum_{k=0}^n\binom nk x^{n-k}y^k

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

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

計算二項式係數[编辑]

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

遞歸公式[编辑]

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

  \binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \forall n,k\in\N

其中特別指定:

\binom n0 = 1 \quad \forall n\in\N\cup\{0\},
\binom 0k = 0 \quad \forall k\in\N.

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

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

乘數公式[编辑]

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

\binom nk = \frac{n^{\underline k}}{k!} = \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k(k-1)(k-2)\cdots 1}=\prod_{i=1}^k \frac{n-(k-i)}{i},

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

階乘公式[编辑]

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

 \binom nk = \frac{n!}{k!\,(n-k)!} \quad \mbox{for }\ 0\leq k\leq n.

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

   

 \binom nk = \binom n{n-k} \quad \mbox{for }\ 0\leq k\leq n.

 

 

 

 

(1)

   

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

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

\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}
  \quad\mbox{for } k\in\N \mbox{ and arbitrary } \alpha.

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

   

 (1+X)^\alpha = \sum_{k=0}^\infty {\alpha \choose k} X^k.

 

 

 

 

(2)

   

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

(1+X)^\alpha(1+X)^\beta=(1+X)^{\alpha+\beta} \quad\mbox{and}\quad ((1+X)^\alpha)^\beta=(1+X)^{\alpha\beta}.

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

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

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

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

   

 {n \choose k} +  {n \choose k+1} = {n+1 \choose k+1},

 

 

 

 

(3)

   

此式可以用於數學歸納法,以証明 \tbinom n k對於所有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橫行列出 \tbinom n kk = 0,…,n項,其建構方法為在外邊填上1,然後將上一行中每兩個相鄰數相加的和填在其下,此方法可快速地計算二項式係數而不涉及乘法或分數,例如從第5橫行可馬上得出

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

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

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

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

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

就任就非負整數k\scriptstyle{\binom{t}{k}}可表達為一多項式除以k!:

\binom{t}{k} =\frac{(t)_k}{k!}=\frac{(t)_k}{(k)_k}= \frac{t(t-1)(t-2)\cdots(t-k+1)}{k(k-1)(k-2)\cdots(2)(1)};\,\!

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

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

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

\binom{t}{k} = \sum_{i=0}^k \frac{s_{k,i}}{k!} t^i

\tbinom{t}{k}導數可以對數微分計算:

\frac{\mathrm{d}}{\mathrm{d}t} \binom{t}{k} = \binom{t}{k} \sum_{i=0}^{k-1} \frac{1}{t-i}\,.

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

在任何包含Q中,最多d階的多項式有惟一的線性組合\sum_{k=0}^d a_k \binom{t}{k}。係數ak是數列p(0), p(1), …, p(k)的k差分,亦即: [6]

   

a_k = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} p(i).

 

 

 

 

(3.5)

   

整數值多項式[编辑]

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

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

9\tbinom{t}{2} + 6 \tbinom{t}{1} + 0\tbinom{t}{0}

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

\begin{pmatrix} \tbinom{t-1}{0} & \tbinom{t-1}{1} & \tbinom{t-1}{2} \end{pmatrix} \begin{pmatrix} 1 & 0 & 0 \\-1 & 1 & 0\\1 & -2 & 1 \end{pmatrix} \begin{pmatrix} 6 \\ 21 \\ 45 \end{pmatrix}=\begin{pmatrix} \tbinom{t-1}{0} & \tbinom{t-1}{1} & \tbinom{t-1}{2} \end{pmatrix} \begin{pmatrix} 6 \\ 15 \\ 9 \end{pmatrix}
=6\tbinom{t-1}{0} + 15\tbinom{t-1}{1} + 9\tbinom{t-1}{2}=6\tbinom{t}{1} + 9\tbinom{t}{2}

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

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

关系式[编辑]

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

 \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}

再者:

\binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}.

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

\binom ni \binom im=\binom nm \binom {n-m}{i-m}[7]

一阶求和公式[编辑]

 \sum_{r=0}^n \binom nr = 2^{n}
  •  \sum_{i=m}^n \binom {a+i}{i} = \binom {a+n+1}{n} - \binom {a+m}{m-1}
 \binom {a+m}{m-1} + \binom {a+m}{m} + \binom {a+m+1}{m+1} + ... + \binom {a+n}{n} = \binom {a+n+1}{n}
 F_{n-1}+F_n=\sum_{i=0}^{\infty} \binom {n-1-i}{i}+\sum_{i=0}^{\infty} \binom {n-i}{i}=1+\sum_{i=1}^{\infty} \binom {n-i}{i-1}+\sum_{i=1}^{\infty} \binom {n-i}{i}=1+\sum_{i=1}^{\infty} \binom {n+1-i}{i}=\sum_{i=0}^{\infty} \binom {n+1-i}{i}=F_{n+1}
  •  \sum_{i=m}^n \binom ia = \binom {n+1}{a+1} - \binom {m}{a+1}
 \binom {m}{a+1} + \binom ma + \binom {m+1}a ... + \binom na = \binom {n+1}{a+1}

二阶求和公式[编辑]

(1-x)^{-r_1} (1-x)^{-r_2}=(1-x)^{-r_1-r_2}
(1-x)^{-r_1} (1-x)^{-r_2}=(\sum_{n=0}^{\infty} \binom {r_1+n-1}{r_1-1} x^n)(\sum_{n=0}^{\infty} \binom {r_2+n-1}{r_2-1} x^n)=\sum_{n=0}^{\infty} (\sum_{i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}) x^n
(1-x)^{-r_1-r_2}=\sum_{n=0}^{\infty} \binom {r_1+r_2+n-1}{r_1+r_2-1} x^n
  • \sum_{i=0}^k \binom ni \binom m{k-i}=\binom {n+m}k

三阶求和公式[编辑]

  • {\binom {n+k}k}^2=\sum_{j=0}^k {\binom kj}^2 \binom {n+2k-j}{2k}

備註[编辑]

  1. ^ Higham (1998)
  2. ^ Lilavati 第6節,第4章(見Knuth (1997))。
  3. ^ Shilov (1977)
  4. ^ 見(Graham,Knuth & Patashnik 1994),其中就k<0定義了\tbinom n k = 0,其他一般化形式包括考慮兩參數為實數或複數時以伽瑪函數k<0時定義\tbinom n k,但此舉會令大部分二項式係數的恆等式失效,故未有被廣泛採用。然而,此方法替不等於零的參數下定義則可得出如Hilton, Holton and Pedersen, Mathematical reflections: in a room with many mirrors, Springer, 1997中那種好看的「帕斯卡風車」,但是卻會令帕斯卡法則在原點失效。
  5. ^ Muir, Thomas. Note on Selected Combinations. Proceedings of the Royal Society of Edinburgh. 1902. 
  6. ^ 此可視作泰勒定理的離散形式,亦與牛頓多項式有關,此式的交錯項之和可以Nörlund–Rice積分表示。
  7. ^ 两个排列组合求和公式. 
  8. ^ n次单位根在代数问题中的应用. 
  9. ^ 斐波那契数列与组合数的一个关系及推广. 
  10. ^ 组合数列求和. 

參考文獻[编辑]

外部連結[编辑]

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

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

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

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