# 二項式係數

（重定向自组合数

## 定義及概念

${\displaystyle (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}}$

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

## 計算二項式係數

### 遞歸公式

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

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

### 乘數公式

${\displaystyle {\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}},}$

### 階乘公式

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

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

(1)

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

${\displaystyle {\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 .}$

${\displaystyle (1+X)^{\alpha }=\sum _{k=0}^{\infty }{\alpha \choose k}X^{k}.}$

(2)

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

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

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

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

(3)

 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

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

${\displaystyle (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}}$

## 組合數學和統計學

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

## 以多項式表達二項式係數

${\displaystyle {\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)}};\,\!}$

${\displaystyle {\binom {t}{k}}=\sum _{i=0}^{k}{\frac {s_{k,i}}{k!}}t^{i}}$

${\displaystyle {\tbinom {t}{k}}}$導數可以對數微分計算：

${\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\binom {t}{k}}={\binom {t}{k}}\sum _{i=0}^{k-1}{\frac {1}{t-i}}\,.}$

### 以二項式係數為多項式空間之基底

${\displaystyle a_{k}=\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}p(i).}$

(3.5)

### 整數值多項式

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

${\displaystyle t=1,2,3}$${\displaystyle {\frac {3t(3t+1)}{2}}=6,21,45}$帕斯卡矩阵可算出：

${\displaystyle {\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}}}$
${\displaystyle =6{\tbinom {t-1}{0}}+15{\tbinom {t-1}{1}}+9{\tbinom {t-1}{2}}=6{\tbinom {t}{1}}+9{\tbinom {t}{2}}}$

## 有關二項式係數的恆等式

### 关系式

• ${\displaystyle {\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}}$
• ${\displaystyle {\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}}$
• ${\displaystyle {\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.}$

${\displaystyle {\binom {n}{i}}{\binom {i}{m}}={\binom {n}{m}}{\binom {n-m}{i-m}}}$[参 2]

### 一阶求和公式

• ${\displaystyle \sum _{r=0}^{n}{\binom {n}{r}}=2^{n}}$
• ${\displaystyle \sum _{r=0}^{k}{\binom {n+r-1}{r}}={\binom {n+k}{k}}}$
• ${\displaystyle \sum _{r=0}^{n-k}{\frac {(-1)^{r}(n+1)}{k+r+1}}{\binom {n-k}{r}}={\binom {n}{k}}^{-1}}$
• ${\displaystyle \sum _{r=0}^{n}{\binom {dn}{dr}}={\frac {1}{d}}\sum _{r=1}^{d}(1+e^{\frac {2\pi ri}{d}})^{dn}}$[参 3]
• ${\displaystyle \sum _{i=m}^{n}{\binom {a+i}{i}}={\binom {a+n+1}{n}}-{\binom {a+m}{m-1}}}$
${\displaystyle {\binom {a+m}{m-1}}+{\binom {a+m}{m}}+{\binom {a+m+1}{m+1}}+...+{\binom {a+n}{n}}={\binom {a+n+1}{n}}}$
• ${\displaystyle F_{n}=\sum _{i=0}^{\infty }{\binom {n-i}{i}}}$[参 4]
${\displaystyle 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}}$
• ${\displaystyle \sum _{i=m}^{n}{\binom {i}{a}}={\binom {n+1}{a+1}}-{\binom {m}{a+1}}}$
${\displaystyle {\binom {m}{a+1}}+{\binom {m}{a}}+{\binom {m+1}{a}}...+{\binom {n}{a}}={\binom {n+1}{a+1}}}$

### 二阶求和公式

• ${\displaystyle \sum _{r=0}^{n}{\binom {n}{r}}^{2}={\binom {2n}{n}}}$
• ${\displaystyle \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}}}$[参 5]
${\displaystyle (1-x)^{-r_{1}}(1-x)^{-r_{2}}=(1-x)^{-r_{1}-r_{2}}}$
${\displaystyle (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}}$
${\displaystyle (1-x)^{-r_{1}-r_{2}}=\sum _{n=0}^{\infty }{\binom {r_{1}+r_{2}+n-1}{r_{1}+r_{2}-1}}x^{n}}$
• ${\displaystyle \sum _{i=0}^{k}{\binom {n}{i}}{\binom {m}{k-i}}={\binom {n+m}{k}}}$

### 三阶求和公式

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

## 備註

1. ^
2. ^ Lilavati 第6節，第4章（見Knuth (1997)）。
3. ^
4. ^ 見（Graham，Knuth & Patashnik 1994），其中就${\displaystyle k<0}$定義了${\displaystyle {\tbinom {n}{k}}=0}$，其他一般化形式包括考慮兩參數為實數或複數時以伽瑪函數${\displaystyle k<0}$時定義${\displaystyle {\tbinom {n}{k}}}$，但此舉會令大部分二項式係數的恆等式失效，故未有被廣泛採用。然而，此方法替不等於零的參數下定義則可得出如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).