二項式係數

<image>

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

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

## 歷史及記號

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

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

## 定義及概念

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

$$(1+x)^n=\sum_{k=0}^n\binom nk 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 nk x^{n-k}y^k$$

此數的另一出處在組合數學，表達了從$n$物中，不計較次序取$k$物有多少方式，亦即從一$n$元素集合中所能組成$k$元素子集的數量。此定義與上述定義相同，理由如下：若將冪$(1+X)^n$的$n$個因數逐一標記為$i$（從1至$n$），則任一$k$元素子集則建構成展式中的一個$X^k$項，故此該單項的係數等如此種子集的數量。亦因此，就任何自然數$n$和$k$而言，$\tbinom nk$亦為自然數。此外，二項式係數亦見於很多組合問題的解答中，如由$n$個位元（如數字0或1）組成的所有序列中，其和為$k$的數目為$\tbinom nk$，又如算式$k=a_1+a_2+\cdots+a_n$，其中每一$a_i$均為非負整數，則有$\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)$中的$x^k$項，或點算集合$\left \{ 1,2,\cdots ,n \right \}$的$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$的階乘，此公式從上述乘數公式中分子分母各乘以$(n-k)!$取得，所以此公式中的分子分母有眾同共同因子。除非先行抵銷兩邊中的共同因子，否則以此公式進行計算時較率欠佳，尤因階乘的數值增長特快。惟此公式展示了二項式係數的對稱特性：

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

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

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

$k<0$

$\tbinom n k = 0$

$k<0$

$\tbinom n k$

$$\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} <pre> \quad\mbox{for } k\in\N \mbox{ and arbitrary } \alpha. </pre>$$

此定義能使二項式公式一般化（其中一單項為1），故$\tbinom\alpha k$仍能相稱地稱作二項式係數：

$$(1+X)^\alpha = \sum_{k=0}^\infty {\alpha \choose k} X^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$的其他值，包括負數和有理數，此級數為無窮級數。

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

<image>

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

$${n \choose k} + {n \choose k+1} = {n+1 \choose k+1},$$ 此式可以用於數學歸納法，以証明$\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,\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差分，亦即：

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

### 整數值多項式

每一多項式$\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 ni \binom im=\binom nm \binom {n-m}{i-m}$

### 一階求和公式

- $$\sum_{r=0}^n \binom nr = 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 nk^{-1}$$
- $\sum_{r=0}^n \binom {dn}{dr}=\frac{1}{d}\sum_{r=1}^d (1+e^{\frac{2 \pi r i}{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 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}$$

### 二階求和公式

- $$\sum_{r=0}^n {\binom nr}^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 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}$$

## 參考文獻

- Benjamin, Arthur T.; Quinn, Jennifer (2003). Proofs that Really Count: The Art of Combinatorial Proof , Mathematical Association of America.

## 外部連結

- Calculation of Binomial Coefficient