為與高中教材相契合，本文中的組合數採取蘇式記法

C_{n}^{m}

而不是美式記法

{n \choose m}

二項式定理

n\in\mathbb{N}^{*}

\left( a+b \right)^{n} =\sum_{r=0}^{n}{C_{n}^{r}a^{n-r}b^{r}} =C_{n}^{0}a^{n}+C_{n}^{1}a^{n-1}b+\cdots +C_{n}^{r}a^{n-r}b^{r}+\cdots+C_{n}^{n}b^{n}

這就是

二項式定理

，等式右邊即為

\left( a+b \right)^{n}

的

二項展開式

，它共有

n+1

項

C_{n}^{r}a^{n-r}b^{r}

叫做二項展開式的

第 #FormatImgID_8# 項

，也即

通項

，用

T_{r+1}

表示

T_{r+1}=C_{n}^{r}a^{n-r}b^{r}

C_{n}^{r}

（

r=0,1,2,\cdots,n

）叫做第

r+1

項的

二項式係數

證明：

方法（一）組合證法

將乘積

\left( a+b \right)^{n}= \left( a+b \right)\left( a+b \right)\cdots\left( a+b \right)

按乘法對加法的分配律展開，直至沒有括號

因為每一項都可選

a

或

b

，因此（未合併同類項時）共有

2^{n}

項

顯然所有項都是

a^{n-r}b^{r}

（

r=0,1,2,\cdots,n

）的形式

為了計數形如

a^{n-r}b^{r}

的項的係數，必須從

n

個

a+b

中選取

n-r

個

a

（從而乘積中其餘的

r

個項都是

b

）

所以

a^{n-r}b^{r}

的係數是

C_{n}^{n-r}=C_{n}^{r}

這就證明了二項式定理

方法（二）數學歸納法

\left( a+b \right)^{1} =\sum_{r=0}^{1}{C_{1}^{r}a^{1-r}b^{r}} =C_{1}^{0}a^{1}+C_{1}^{1}b^{1}

當然成立

假設

n=m

時定理成立，即

\left( a+b \right)^{m} =\sum_{r=0}^{m}{C_{m}^{r}a^{m-r}b^{r}} =C_{m}^{0}a^{m}+C_{m}^{1}a^{m-1}b+\cdots +C_{m}^{r}a^{m-r}b^{r}+\cdots+C_{m}^{m}b^{m}

則

n=m+1

時

\begin{alignat}{0} \left( a+b \right)^{m+1} =\left( a+b \right)\left( a+b \right)^{m} =\left( a+b \right)\sum_{r=0}^{m}{C_{m}^{r}a^{m-r}b^{r}}\\ =a\sum_{r=0}^{m}{C_{m}^{r}a^{m-r}b^{r}} +b\sum_{r=0}^{m}{C_{m}^{r}a^{m-r}b^{r}}\\ =\sum_{r=0}^{m}{C_{m}^{r}a^{m+1-r}b^{r}} +\sum_{r=0}^{m}{C_{m}^{r}a^{m-r}b^{r+1}}\\ =C_{m}^{0}a^{m+1} +\sum_{r=1}^{m}{C_{m}^{r}a^{m+1-r}b^{r}} +\sum_{r=0}^{m-1}{C_{m}^{r}a^{m-r}b^{r+1}} +C_{m}^{m}b^{m+1}\\ =C_{m+1}^{0}a^{m+1} +\sum_{r=1}^{m}{C_{m}^{r}a^{m+1-r}b^{r}} +\sum_{r=1}^{m}{C_{m}^{r-1}a^{m+1-r}b^{r}} +C_{m+1}^{m+1}b^{m+1} \end{alignat}

根據之後會講到的組合恆等式

C_{n+1}^{r}=C_{n}^{r}+C_{n}^{r-1}

\begin{alignat}{0} \left( a+b \right)^{m+1}\\ =C_{m+1}^{0}a^{m+1} +\sum_{r=1}^{m}{C_{m}^{r}a^{m+1-r}b^{r}} +\sum_{r=1}^{m}{C_{m}^{r-1}a^{m+1-r}b^{r}} +C_{m+1}^{m+1}b^{m+1}\\ =C_{m+1}^{0}a^{m+1} +\sum_{r=1}^{m}{C_{m+1}^{r}a^{m+1-r}b^{r}} +C_{m+1}^{m+1}b^{m+1}\\ =\sum_{r=0}^{m+1}{C_{m+1}^{r}a^{m+1-r}b^{r}} \end{alignat}

這樣便由數學歸納法證明了二項式定理

二項式係數的性質

（1）

對稱性

C_{n}^{k}=C_{n}^{n-k}

證明：

方法（一）

直接由定義

C_{n}^{k}=\frac{n(n-1)\cdots(n-k+2)(n-k+1)}{k!}=\frac{n!}{k!(n-k)!}

C_{n}^{n-k}=\frac{n(n-1)\cdots(k+1)}{(n-k)!} =\frac{n!}{k!(n-k)!}

方法（二）

注意到組合學上的意義，從

n

個元素中選

k

個元素，與從

n

個元素中選出

n-k

個元素再剔除掉，保留剩下

k

個是等價的

（2）

單峰性

n

為偶數時

C_{n}^{0}<C_{n}^{1}<\cdots<C_{n}^{n/2-1}<C_{n}^{n/2}

C_{n}^{n/2}>C_{n}^{n/2+1}>\cdots>C_{n}^{n-1}>C_{n}^{n}

n

為奇數時

C_{n}^{0}<C_{n}^{1}<\cdots<C_{n}^{(n-1)/2}=C_{n}^{(n+1)/2}

C_{n}^{(n-1)/2}=C_{n}^{(n+1)/2}>\cdots>C_{n}^{n-1}>C_{n}^{n}

證明：

令

1\leq k\leq n

我們考慮

C_{n}^{k-1}

與

C_{n}^{k}

的比值

\frac{C_{n}^{k}}{C_{n}^{k-1}} =\cfrac{\cfrac{n!}{k!(n-k)!}}{\cfrac{n!}{(k-1)!(n-k+1)!}} =\frac{n-k+1}{k}

透過比較

n-k+1

與

k

的大小，即可比較

C_{n}^{k}

與

C_{n}^{k-1}

的大小

1）當

n

為偶數時

若

k\leq\frac{n}{2}

n-k+1\geq n-\frac{n}{2}+1>\frac{n}{2}\geq k

這就得到

C_{n}^{k}>C_{n}^{k-1}

若

k\geq\frac{n}{2}+1

n-k+1\leq n-(\frac{n}{2}+1)+1=\frac{n}{2}<k

這就得到

C_{n}^{k}<C_{n}^{k-1}

2）當

n

為奇數時

若

k=\frac{n+1}{2}

n-k+1=n-\frac{n+1}{2}+1=\frac{n+1}{2}=k

這就得到

C_{n}^{(n-1)/2}=C_{n}^{(n+1)/2}

若

k\leq\frac{n-1}{2}

n-k+1\geq n-\frac{n-1}{2}+1>\frac{n+1}{2}\geq k

這就得到

C_{n}^{k}>C_{n}^{k-1}

若

k>\frac{n+1}{2}

n-k+1<n-\frac{n+1}{2}+1=\frac{n+1}{2}<k

這就得到

C_{n}^{k}<C_{n}^{k-1}

綜上，命題得證

（3）

\sum_{r=0}^{n}{C_{n}^{r}}= C_{n}^{0}+C_{n}^{1}+\cdots+C_{n}^{n}=2^{n}

證明：

方法（一）

二項式定理中，令

a=1

，

b=1

2^{n}=\left( 1+1 \right)^{n} =\sum_{r=0}^{n}{C_{n}^{r}} =C_{n}^{0}+C_{n}^{1}+\cdots+C_{n}^{n}

即可

方法（二）

一個

n

元素集合恰好有

2^{n}

個子集（子集的集合也即冪集）

每個子集可能有

0

個元素、

1

個元素、…、

n

個元素

具有

0

個元素的子集有

C_{n}^{0}

個

具有

1

個元素的子集有

C_{n}^{1}

個

具有

2

個元素的子集有

C_{n}^{2}

個

…

具有

n

個元素的子集有

C_{n}^{n}

個

\sum_{r=0}^{n}{C_{n}^{r}} =C_{n}^{0}+C_{n}^{1}+\cdots+C_{n}^{n}

即是該

n

元素集合的子集的個數，等於

2^{n}

命題得證

（4）

\sum_{r=0}^{n}{\left( -1 \right)^{k}C_{n}^{r}}= C_{n}^{0}-C_{n}^{1}+\cdots+\left( -1 \right)^{n}C_{n}^{n} =0

證明：

方法（一）

二項式定理中，令

a=1

，

b=-1

0^{n}=\left( 1-1 \right)^{n} =\sum_{r=0}^{n}{\left( -1 \right)^{k}C_{n}^{r}}= C_{n}^{0}-C_{n}^{1}+\cdots+\left( -1 \right)^{n}C_{n}^{n}

即可

它的一個推論是

奇數項的二項式係數之和與偶數項的二項式係數之和相等，即

C_{n}^{0}+C_{n}^{2}+C_{n}^{4}+\cdots= C_{n}^{1}+C_{n}^{3}+C_{n}^{5}+\cdots

方法（二）

設

T

是一個有

n

個元素的集合，對

T

中任意一個元素

a

從

T

中選取

r

個元素，從元素

a

的角度講，這

r

個元素的組合只分包含

a

和不含

a

兩類

若

r

為奇數時，這個組合裡含有

a

，去掉

a

便得到一個

r

為偶數的組合

若

r

為奇數時，這個組合裡不含

a

，加上

a

便得到一個

r

為偶數的組合

但是所有組合要麼含

a

要麼不含

a

這就說明

r

為奇數的組合與

r

為偶數的組合是一一對應的

（5）

\sum_{r=0}^{n}{2^{r}C_{n}^{r}}= C_{n}^{0}+2C_{n}^{1}+\cdots+2^{n}C_{n}^{n}=3^{n}

證明：

二項式定理中，令

a=1

，

b=2

3^{n}=\left( 1+2 \right)^{n}=\sum_{r=0}^{n}{2^{r}C_{n}^{r}} =C_{n}^{0}+2C_{n}^{1}+\cdots+2^{n}C_{n}^{n}

即可

（6）

\sum_{r=1}^{n}{r\cdot C_{n}^{r}}= C_{n}^{1}+2\cdot C_{n}^{2}+\cdots+n\cdot C_{n}^{n}=n\cdot2^{n-1}

證明：

只要對等式

\left( 1+x \right)^{n} =\sum_{r=0}^{n}{C_{n}^{r}x^{r}} =C_{n}^{0}+C_{n}^{1}x+\cdots+C_{n}^{n}x^{n}

兩邊對

x

求導，再代入

x=1

即可

（7）

帕斯卡恆等式

設

n,k\in\mathbb{N}^{*}

，

n\geq k

C_{n+1}^{k}=C_{n}^{k}+C_{n}^{k-1}

證明：

方法（一）

C_{n}^{k-1}=\frac{n!}{(k-1)!(n-k+1)!} =\frac{n(n-1)\cdots(n-k+2)}{\left( k-1 \right)!}

C_{n}^{k}=\frac{n!}{k!(n-k)!} =\frac{n(n-1)\cdots(n-k+2)(n-k+1)}{k!}

\begin{alignat}{0} C_{n}^{k}+C_{n}^{k-1}\\ =\frac{n(n-1)\cdots(n-k+2)}{\left( k-1 \right)!}+ \frac{n(n-1)\cdots(n-k+2)(n-k+1)}{k!}\\ =\frac{n(n-1)\cdots(n-k+2)k}{k!}+ \frac{n(n-1)\cdots(n-k+2)(n-k+1)}{k!}\\ =\frac{(n+1)n(n-1)\cdots(n-k+2)}{k!}\\ =C_{n+1}^{k} \end{alignat}

方法（二）

設

T

是一個有

n+1

個元素的集合，其中一個元素為

a\in T

設集合

S

是集合

T

去掉元素

a

後的子集，即

S=T-\left\{ a \right\}

顯然

T

中包含

k

個元素的子集有

C_{n+1}^{k}

個

這些子集，要麼不包含

a

，但包含集合

S

中的

k

個元素

要麼包含

a

，以及包含集合

S

中的

k-1

個元素

集合

S

中包含

k

個元素的子集有

C_{n}^{k}

個，所以

T

的不包含

a

的

k

元子集有

C_{n}^{k}

個

集合

S

中包含

k-1

個元素的子集有

C_{n}^{k-1}

個，所以

T

的包含

a

的

k

元子集有

C_{n}^{k-1}

個

而集合

T

的

k

元子集要麼包含元素

a

，要麼不包含元素

a

所以它總共有

C_{n}^{k}+C_{n}^{k-1}

個

所以有

C_{n+1}^{k}=C_{n}^{k}+C_{n}^{k-1}

參考資料

Kenneth H。Rosen《離散數學及其應用》，機械工業出版社

Sheldon M。Ross《機率論基礎教程》，機械工業出版社

許胤龍、孫淑玲《組合數學引論》，中國科學技術大學出版社