二項式係數

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

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

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

二項式係數亦有不同的符號表達方式，包括：C(n, k)、_nC_k、ⁿC_k、 $\scriptstyle C_{n}^{k}$ 、 $\scriptstyle C_{k}^{n}$ ^[3]，其中的C代表組合（combinations）或選擇（choices）。

定義及概念

考慮包含0的自然數n和k，則二項式係數 ${\tbinom {n}{k}}$ 定義為(1 + X)ⁿ的展式中，單項X^k的係數，亦即在二項式定理中的係數

(x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{n-k}y^{k}

（任何交換環元素x、y中有定義），亦因此得名為「二項式係數」。

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

計算二項式係數

除展開二項式或點算組合數量之外，尚有多種方式計算 ${\tbinom {n}{k}}$ 的值。

遞歸公式

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

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

其中特別指定：

{\binom {n}{0}}=1\quad \forall n\in \mathbb {N} \cup \{0\},

{\binom {0}{k}}=0\quad \forall k\in \mathbb {N} .

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

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

乘數公式

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

{\binom {n}{k}}={\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 {n}{k}}={\frac {n!}{k!\,(n-k)!}}\quad {\mbox{for }}\ 0\leq k\leq n.

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

{\binom {n}{k}}={\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 \mathbb {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的項為零，此無窮級數變成有限項的和，還原為二項式公式，但對於α的其他值，包括負數和有理數，此級數為無窮級數。

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

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

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

3

此式可以用於數學歸納法，以証明 ${\tbinom {n}{k}}$ 對於所有n和k均為自然數（等同於証明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:		1		7		21		35		35		21		7		1
8:	1		8		28		56		70		56		28		8		1

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

(x + y)⁵ = 1 x⁵ + 5 x⁴y + 10 x³y² + 10 x²y³ + 5 x y⁴ + 1 y⁵

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

組合數學和統計學

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

共有 ${\tbinom {n}{k}}$ 種方式從n元素中選取k項。見組合。
共有 ${\tbinom {n+k-1}{k}}$ 種方式從一個n元素集合中選取（容許重覆選取）k元素建立多重集。
共有 ${\tbinom {n+k}{k}}$ 個字符串包含k個1和n個零。
共有 ${\tbinom {n+1}{k}}$ 個字符串包含k個1和n個零，且沒有兩個1相鄰。^[5]
卡塔蘭數是 ${\frac {\tbinom {2n}{n}}{n+1}}$
統計學中的二項式分佈是 ${\tbinom {n}{k}}p^{k}(1-p)^{n-k}\!$
貝茲曲線的公式。

以多項式表達二項式係數

就任就非負整數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}}$ 。係數a_k是數列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+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}$
${\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 {n}{i}}{\binom {i}{m}}={\binom {n}{m}}{\binom {n-m}{i-m}}

^[7]

一阶求和公式

$\sum _{r=0}^{n}{\binom {n}{r}}=2^{n}$
$\sum _{r=0}^{n}{\binom {dn}{dr}}={\frac {1}{d}}\sum _{r=1}^{d}(1+e^{\frac {2\pi ri}{d}})^{dn}$ ^[8]
$\sum _{r=0}^{n}r^{m}{\binom {n}{r}}=n(n-1)\cdots (n-m+1)2^{n-m}$

(1+e^{x})^{n}=\sum _{r=0}^{n}e^{rx}{\binom {n}{r}}

n(n-1)\cdots (n-m+1)(1+e^{0})^{n-m}=\sum _{r=0}^{n}r^{m}e^{0}{\binom {n}{r}}

$\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}=\sum _{i=0}^{\infty }{\binom {n-i}{i}}$ ^[9]

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 {i}{a}}={\binom {n+1}{a+1}}-{\binom {m}{a+1}}$

{\binom {m}{a+1}}+{\binom {m}{a}}+{\binom {m+1}{a}}...+{\binom {n}{a}}={\binom {n+1}{a+1}}

二阶求和公式

$\sum _{i=0}^{n}{\binom {r_{1}+n-1-i}{r_{1}-1}}{\binom {r_{2}+i-1}{r_{2}-1}}={\binom {r_{1}+r_{2}+n-1}{r_{1}+r_{2}-1}}$ ^[10]

(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 {n}{i}}{\binom {m}{k-i}}={\binom {n+m}{k}}$

三阶求和公式

${\binom {n+k}{k}}^{2}=\sum _{j=0}^{k}{\binom {k}{j}}^{2}{\binom {n+2k-j}{2k}}$

備註

^ Higham (1998)
^ Lilavati 第6節，第4章（見Knuth (1997)）。
^ Shilov (1977)
^ 見(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中那種好看的「帕斯卡風車」，但是卻會令帕斯卡法則在原點失效。
^ Muir, Thomas. Note on Selected Combinations. Proceedings of the Royal Society of Edinburgh. 1902.
^ 此可視作泰勒定理的離散形式，亦與牛頓多項式有關，此式的交錯項之和可以Nörlund–Rice積分表示。
^ 两个排列组合求和公式.
^ n次单位根在代数问题中的应用.
^ 斐波那契数列与组合数的一个关系及推广.
^ 组合数列求和.

參考文獻

Benjamin, Arthur T.; Quinn, Jennifer (2003). Proofs that Really Count: The Art of Combinatorial Proof , Mathematical Association of America.
Bryant, Victor. Aspects of combinatorics. Cambridge University Press. 1993. ISBN 0521419743.
Flum, Jörg; Grohe, Martin. Parameterized Complexity Theory. Springer. 2006. ISBN 978-3-540-29952-3.
Fowler, David. The Binomial Coefficient Function. The American Mathematical Monthly (Mathematical Association of America). 1996, 103 (1): 1–17. JSTOR 2975209. doi:10.2307/2975209. 已忽略未知参数|month=（建议使用|date=） (帮助)
Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. Concrete Mathematics Second. Addison-Wesley. 1994: 153–256. ISBN 0-201-55802-5.
Higham, Nicholas J. Handbook of writing for the mathematical sciences. SIAM. 1998: 25. ISBN 0898714206.
Knuth, Donald E. The Art of Computer Programming, Volume 1: Fundamental Algorithms Third. Addison-Wesley. 1997: 52–74. ISBN 0-201-89683-4.
Singmaster, David. Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients. J. London Math. Soc. (2). 1974, 8 (3): 555–560. doi:10.1112/jlms/s2-8.3.555.
Shilov, G. E. Linear algebra. Dover Publications. 1977. ISBN 9780486635187.

外部連結

Calculation of Binomial Coefficient

本條目含有来自PlanetMath《Binomial Coefficient》的內容，版权遵守知识共享协议：署名-相同方式共享协议。

本條目含有来自PlanetMath《Bounds for binomial coefficients》的內容，版权遵守知识共享协议：署名-相同方式共享协议。

本條目含有来自PlanetMath《Proof that C(n,k) is an integer》的內容，版权遵守知识共享协议：署名-相同方式共享协议。

本條目含有来自PlanetMath《Generalized binomial coefficients》的內容，版权遵守知识共享协议：署名-相同方式共享协议。

[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] 次单位根在代数问题中的应用.

[9] 斐波那契数列与组合数的一个关系及推广.

[10] 组合数列求和.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]