组合数

在數學上，**二項式係數**是二項式定理中各項的係數。一般而言，二項式係數由兩個非負整數 $n$ 和 $k$ 為參數決定，寫作 ${\tbinom {n}{k}}$ ，定義為 $(1+x)^{n}$ 的多項式展開式中， $x^{k}$ 項的係數，因此一定是非負整數。如果將二項式係數 ${\binom {n}{0}},{\binom {n}{1}},\dots ,{\binom {n}{n}}$ 寫成一行，再依照 $n=0,1,2,\dots $ 順序由上往下排列，則構成帕斯卡三角形。

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

## 歷史及記號

雖然二項式係數在西元 10 世紀就已經被發現（見帕斯卡三角形），但表達式 ${\tbinom {n}{k}}$ 卻是到 1826 年才由安德烈亞斯・馮・厄廷格豪森首次始用。最早探討二項式係數的論述是十世紀的 Halayudha 寫的印度教典籍《Pingala 的計量聖典》（chandaḥśāstra）。約 1150 年，印度數學家 Bhaskaracharya 於其著作《Lilavati》 中給出一個簡單的描述。

二項式係數亦有不同的符號表達方式，包括： $C(n,k)$ 、 $_{n}C_{k}$ 、 $^{n}C_{k}$ 、 $C_{n}^{k}$ 、 $C_{k}^{n}$ ，其中的 C 代表組合（combinations）或選擇（choices）。很多計算機使用含有 C 的變種記號，使得算式只佔一行的空間，相同理由也發生在置換數 $P_{k}^{n}$ ，例如寫作 P (_n_, _k_)。

## 定義及概念

對於非負整數 $n$ 和 $k$ ，二項式係數 ${\tbinom {n}{k}}$ 定義為 $(1+x)^{n}$ 的多項式展開式中， $x^{k}$ 項的係數，即

　
: $(1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}={\binom {n}{0}}+{\binom {n}{1}}x+\cdots +{\binom {n}{n}}x^{n}$

事實上，若 $x$ 、 $y$ 為交換環上的元素，則

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

此數的另一出處在組合數學，表達了從 _$n$_ 物中，不計較次序取 _$k$_ 物有多少方式，亦即從一 _$n$_ 元素集合中所能組成 _$k$_ 元素子集的數量。此定義與上述定義相同，理由如下：若將冪 $(1+X)^{n}$ 的 _$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)^{n-1}(1+x)$ 中的 _$x^{k}$_ 項，或點算集合 $\left\{1,2,\cdots ,n\right\}$ 的 _$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)!$ 取得，所以此公式中的分子分母有眾同共同因子。除非先行抵銷兩邊中的共同因子，否則以此公式進行計算時較率欠佳，尤因階乘的數值增長特快。惟此公式展示了二項式係數的對稱特性：

　
:

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

若將 _$n$_ 換成任意數值（負數、實數或複數） $\alpha $ ，甚至是在任何能為正整數給出逆元素的交換環中的一元素，則二項式係數可籍乘數公式擴展：

　
: ${\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}}$ 仍能相稱地稱作二項式係數：

　
:

此公式對任何複數 _$\alpha $_ 及 $X$ ， $\left\vert X\right\vert <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 }.$

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

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

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

　
:

此式可以用於數學歸納法，以証明 ${\tbinom {n}{k}}$ 對於所有 _$n$_ 和 _$k$_ 均為自然數（等同於証明 $k!$ 為所有 _$k$_ 個連續整數之積的因數），此特性並不易從公式 (1) 中得出。

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

　
:

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

　
: $(x+y)^{5}={\boldsymbol {1}}x^{5}+{\boldsymbol {5}}x^{4}y+{\boldsymbol {10}}x^{3}y^{2}+{\boldsymbol {10}}x^{2}y^{3}+{\boldsymbol {5}}xy^{4}+{\boldsymbol {1}}y^{5}$

在斜線上相鄰項的差就是上一斜線上的數值，此乃上述遞歸等式 (**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 相鄰。
* 卡塔蘭數是 ${\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)=\ldots =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),\ldots ,p(k)$ 的第 _k_ 差分，亦即：

　
:

### 整數值多項式

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

整數值多項式 ${\frac {3t(3t+1)}{2}}$ 可表達作：

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

從 $t=1,2,3$ 時 ${\frac {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}}$

### 一階求和公式

 * $\sum _{r=0}^{n}{\binom {n}{r}}=2^{n}$
* $\sum _{r=0}^{k}{\binom {n+r-1}{r}}={\binom {n+k}{k}}$
* $\sum _{r=0}^{n-k}{\frac {(-1)^{r}(n+1)}{k+r+1}}{\binom {n-k}{r}}={\binom {n}{k}}^{-1}$
* $\sum _{r=0}^{n}{\binom {dn}{dr}}={\frac {1}{d}}\sum _{r=1}^{d}(1+e^{\frac {2\pi ri}{d}})^{dn}$

　
: * $\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}}$

　
: $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 _{r=0}^{n}{\binom {n}{r}}^{2}={\binom {2n}{n}}$

　
: * $\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}}$

　
: $(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}}$

## 備註

## 參考文獻

* 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 [2011-07-28]. ISBN978-3-540-29952-3. （原始內容存檔於 2007-11-18）.
* Fowler, David. The Binomial Coefficient Function. The American Mathematical Monthly (Mathematical Association of America). January 1996, **103** (1): 1–17. JSTOR 2975209. doi:10.2307/2975209.
* 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》的內容，版權遵守創用 CC 協議：署名 - 相同方式共享協議。
* 本條目含有來自 PlanetMath《Bounds for binomial coefficients》的內容，版權遵守創用 CC 協議：署名 - 相同方式共享協議。
* 本條目含有來自 PlanetMath《C (n,k) is an integer》的內容，版權遵守創用 CC 協議：署名 - 相同方式共享協議。
* 本條目含有來自 PlanetMath《Generalized binomial coefficients》的內容，版權遵守創用 CC 協議：署名 - 相同方式共享協議。