二項式係數公式

本文的閱讀等級:初級

\Psi 表示 n 個元素構成的集合。從 \Psi 中選取 k 個元素的可能方式稱為組合,譬如,從 \Psi=\{a,b,c,d,e\} 選取 3 個元素的組合如下:

abc,~~abd,~~abe,~~ acd,~~ ace,~~ ade,~~ bcd,~~ bce,~~ bde,~~ cde

計算 \Psik—組合數並不困難:想像 n 個元素排成一列,選取領先的 k 個元素,共有 n(n-1)\cdots(n-k+1) 種可能。這 k 個元素可以任意置換,每一種 k—組合重複出現 k! 次。所以,從包含 n 個元素的集合 \Psi 中選取 k 個元素的組合數,記為 \binom{n}{k},計算如下:

\displaystyle  \binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots(1)}

譬如,\binom{5}{3}=\frac{5\cdot 4\cdot 3}{3\cdot 2\cdot 1}=10。我們稱 \binom{n}{k} 為二項式係數 (binomial coefficient)。這個名稱的由來係因

\displaystyle  (a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^{k}

其中 \binom{n}{k}a^{n-k}b^k 的係數。從二項式係數的表達式可知縱使 n 不是整數,我們依然能定義 \binom{n}{k}。為便於識別,我們用 r 代表任一實數,k 代表任一整數,定義

\displaystyle  \binom{r}{k}=\frac{r(r-1)\cdots(r-k+1)}{k(k-1)\cdots(1)}=\prod_{1\le j\le k}\left(\frac{r+1-j}{j}\right),~~k\ge 0;

\displaystyle  \binom{r}{k}=0,~~k<0

見下表,非零的部分稱為帕斯卡三角形 (見“特殊矩陣 (15):Pascal 矩陣 (上)”):

\begin{array}{ccccccccccc}  r&\vline&\binom{r}{0}&\binom{r}{1}&\binom{r}{2}&\binom{r}{3}&\binom{r}{4}&\binom{r}{5}&\binom{r}{6}&\binom{r}{7}&\binom{r}{8}\\[0.3em]  \hline  0&\vline&1&0&0&0&0&0&0&0&0\\  1&\vline&1&1&0&0&0&0&0&0&0\\  2&\vline&1&2&1&0&0&0&0&0&0\\  3&\vline&1&3&3&1&0&0&0&0&0\\  4&\vline&1&4&6&4&1&0&0&0&0\\  5&\vline&1&5&10&10&5&1&0&0&0\\  6&\vline&1&6&15&20&15&6&1&0&0\\  7&\vline&1&7&21&35&35&21&7&1&0\\  8&\vline&1&8&28&56&70&56&28&8&1 \\ \hline  \end{array}

 
二項式係數的應用非常廣泛,不僅見於級數求和、算法分析、組合數學和機率統計,幾乎各個領域都有它的蹤影。二項式係數公式相當龐雜且缺少直觀意義,故不容易掌握它的運算技巧。本文整理了一些基本常用的二項式係數公式[1]。以下用 \mathbb{Z} 表示整數,\mathbb{N} 表示自然數。

 
(1) 階乘表達式:由定義立刻得知

\displaystyle  \binom{n}{k}=\frac{n!}{k!(n-k)!},~~n,k\in\mathbb{N},~n\ge k

 
(2) 對稱公式:由定義和 (1),可得

\displaystyle  \binom{n}{k}=\binom{n}{n-k},~~n\in\mathbb{N},~k\in\mathbb{Z}

k 是負數或大於 n,則 \binom{n}{k}=0

 
(3) 進出公式:由定義可得

\displaystyle  \binom{r}{k}=\frac{r}{k}\binom{r-1}{k-1},~~k\in\mathbb{Z},~k\neq 0

進出公式非常有用,它可以用來合併兩個二項式係數,見 (4)。使用兩次對稱公式 (2) 和進出公式 (3),可推論

\displaystyle  \binom{r}{k}=\binom{r}{r-k}=\frac{r}{r-k}\binom{r-1}{r-1-k}=\frac{r}{r-k}\binom{r-1}{k},~~r\neq k

上式亦可寫為

\displaystyle  r\binom{r-1}{k}=(r-k)\binom{r}{k}

 
(4) 加法公式:或稱為帕斯卡 (Pascal) 法則,如下:

\displaystyle  \binom{r}{k}=\binom{r-1}{k}+\binom{r-1}{k-1},~~k\in\mathbb{Z}

證明如下:利用進出公式 (3) 及其推論,

\displaystyle  r\binom{r-1}{k}+r\binom{r-1}{k-1}=(r-k)\binom{r}{k}+k\binom{r}{k}=r\binom{r}{k}

加法公式常用於整數 k 的歸納證明。

 
(5) 求和公式:利用加法公式 (4) 可證明

\displaystyle  \sum_{k=0}^n\binom{r+k}{k}=\binom{r}{0}+\binom{r+1}{1}+\cdots+\binom{r+n}{n}=\binom{r+n+1}{n},~~n\in\mathbb{N}

證明如下:

\displaystyle\begin{aligned}  \binom{r+n+1}{n}&=\binom{r+n}{n}+\binom{r+n}{n-1}\\  &=\binom{r+n}{n}+\binom{r+n-1}{n-1}+\binom{r+n-1}{n-2}\\  &\vdots\\  &=\binom{r+n}{n}+\binom{r+n-1}{n-1}+\cdots+\binom{r+1}{1}+\binom{r+1}{0}\\  &=\binom{r+n}{n}+\binom{r+n-1}{n-1}+\cdots+\binom{r+1}{1}+\binom{r}{0}+\binom{r}{-1}\\  &=\binom{r+n}{n}+\binom{r+n-1}{n-1}+\cdots+\binom{r+1}{1}+\binom{r}{0},\end{aligned}

最後一個項使用定義 \binom{r}{-1}=0。利用求和公式 (5) 並連續運用對稱公式 (2),可得

\displaystyle \begin{aligned}  \sum_{k=0}^n\binom{k}{m}&=\sum_{k'=-m}^{n-m}\binom{m+k'}{m}\\  &=\sum_{k'=-m}^{-1}\binom{m+k'}{k'}+\sum_{k'=0}^{n-m}\binom{m+k'}{k'}\\  &=0+\binom{m+(n-m)+1}{n-m}=\binom{n+1}{m+1},\end{aligned}

上式中,m,n\in\mathbb{N}。這個求和公式非常管用,譬如,若 m=1,則得我們熟悉的等差級數公式:

\displaystyle   \sum_{k=0}^n\binom{k}{1}=0+1+\cdots+n=\binom{n+1}{2}=\frac{(n+1)n}{2}

欲計算 1^2+2^2+\cdots+n^2,考慮 k^2=k(k-1)+k=2\binom{k}{2}+\binom{k}{1},則

\displaystyle \begin{aligned}  \sum_{k=0}^nk^2&=\sum_{k=0}^n\left(2\binom{k}{2}+\binom{k}{1}\right)=2\binom{n+1}{3}+\binom{n+1}{2}\\  &=2\frac{(n+1)n(n-1)}{6}+\frac{(n+1)n}{2}  =\frac{1}{6}n(n+1)(2n+1).\end{aligned}

 
(6) 上指標相反數公式:利用定義,可得

\displaystyle   \binom{-r}{k}=(-1)^k\binom{r+k-1}{k},~~k\in\mathbb{Z}

將分子的每一項改成相反數,推導如下:

\displaystyle \begin{aligned}  \binom{-r}{k}&=\frac{(-r)(-r-1)\cdots(-r-k+1)}{k(k-1)\cdots(1)}\\  &=(-1)^k\frac{r(r+1)\cdots(r+k-1)}{k(k-1)\cdots(1)}\\  &=(-1)^k\binom{r+k-1}{k}.\end{aligned}

利用此公式可證明

\displaystyle   \sum_{k=0}^n\binom{r}{k}(-1)^k=(-1)^n\binom{r-1}{n},~~n\in\mathbb{N}

使用兩次 (6) 及求和公式 (5),

\displaystyle   \sum_{k=0}^n\binom{r}{k}(-1)^k=\sum_{k=0}^n\binom{-r+k-1}{k}=\binom{-r+n}{n}=(-1)^n\binom{r-1}{n}

 
(7) 二項式定理

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

因為

\displaystyle   (x+y)^n=\underbrace{(x+y)(x+y)\cdots(x+y)}_{n}

乘開後每一項的形式為 x^{n-k}y^k,其中 0\le k\le n。對於特定 kx^{n-k}y^k 的係數即為從 n 個因式 (x+y) 選取 ky 的組合數,即 \binom{n}{k}

 
(8) 乘法公式:兩二項式係數相乘有多種公式,下為一例,

\displaystyle   \binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k},~~m,k\in\mathbb{Z}

下面提供當 r\ge m0\le k\le m 的證明。利用階乘公式 (1),

\displaystyle \begin{aligned}  \binom{r}{m}\binom{m}{k}&=\frac{r!m!}{m!(r-m)!k!(m-k)!}\\  &=\frac{r!(r-k)!}{k!(r-k)!(m-k)!(r-m)!}\\  &=\binom{r}{k}\binom{r-k}{m-k}.\end{aligned}

k=1,上式即為進出公式 (3)。

(9) 乘積之和:最重要的乘積之和公式為

\displaystyle   \sum_{k=0}^n\binom{r}{k}\binom{p}{n-k}=\binom{r+p}{n},~~n\in\mathbb{Z}

將二項式定理 (7) 的 y 設為 y=1,就有

\displaystyle   \sum_{k=0}^r\binom{r}{k}x^k=(1+x)^r,~~r\in\mathbb{N}

rp 是正整數,則

\displaystyle \begin{aligned}  \sum_{n=0}^{p+r}\binom{p+r}{n}x^n&=(1+x)^{p+r}=(1+x)^p(1+x)^r\\  &=\sum_{i=0}^{p}\binom{p}{i}x^i\sum_{k=0}^r\binom{r}{k}x^k\\  &=\sum_{n=0}^{p+r}\sum_{k=0}^n\binom{p}{n-k}x^{n-k}\binom{r}{k}x^k\\  &=\sum_{n=0}^{p+r}\left(\sum_{k=0}^n\binom{p}{n-k}\binom{r}{k}\right)x^n  \end{aligned}

比較等號兩邊 x^n 的係數即得證。

 
下面我們來做幾個練習問題。

例一:計算 \displaystyle \sum_{k=1}^nk\binom{n}{k}=\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}

基本思路是設法使用進出公式 (3) 使將求和指標嵌入二項式係數。利用

\displaystyle  k\binom{n}{k}=n\binom{n-1}{k-1}

可得

\displaystyle  \sum_{k=1}^nk\binom{n}{k}=\sum_{k=1}^nn\binom{n-1}{k-1}=n\sum_{k=0}^{n-1}\binom{n-1}{k}=n(1+1)^{n-1}=n2^{n-1}

 
例二:計算 \displaystyle \sum_{k=0}^n\frac{1}{k+1}\binom{n}{k}=1+\frac{1}{2}\binom{n}{1}+\frac{1}{3}\binom{n}{2}+\cdots+\frac{1}{n+1}\binom{n}{n}

類似例一的作法。因為

\displaystyle  \binom{n+1}{k+1}=\frac{n+1}{k+1}\binom{n}{k}

則有

\displaystyle\begin{aligned}  \sum_{k=0}^n\frac{1}{k+1}\binom{n}{k}&=\sum_{k=0}^n\frac{1}{n+1}\binom{n+1}{k+1}=\frac{1}{n+1}\sum_{k=1}^{n+1}\binom{n+1}{k}\\  &=\frac{1}{n+1}\left(\sum_{k=0}^{n+1}\binom{n+1}{k}-\binom{n+1}{0}\right)\\  &=\frac{1}{n+1}\left(2^{n+1}-1\right)  .\end{aligned}

 
例三:計算 \displaystyle \sum_{k=1}^n(-1)^{k+1}\frac{1}{k}\binom{n}{k}=\binom{n}{1}-\frac{1}{2}\binom{n}{2}+\frac{1}{3}\binom{n}{3}-\cdots+(-1)^{n+1}\frac{1}{n}\binom{n}{n}

這個問題要求比較困難的代數技術。反覆使用加法公式 (4) 和進出公式,對於 1\le k\le n

\displaystyle\begin{aligned}  \frac{1}{k}\binom{n}{k}&=\frac{1}{k}\left(\binom{n-1}{k}-\binom{n-1}{k-1}\right)=\frac{1}{k}\binom{n-1}{k}+\frac{1}{n}\binom{n}{k}\\  &=\frac{1}{k}\left(\binom{n-2}{k}+\binom{n-2}{k-1}\right)+\frac{1}{n}\binom{n}{k}\\  &=\frac{1}{k}\binom{n-2}{k}+\frac{1}{n-1}\binom{n-1}{k}+\frac{1}{n}\binom{n}{k}  .\end{aligned}

按照相同方式分解第一項,可得

\displaystyle  \frac{1}{k}\binom{n}{k}=\frac{1}{n}\binom{n}{k}+\frac{1}{n-1}\binom{n-1}{k}+\cdots+\frac{1}{k}\binom{k}{k}

所以,

\displaystyle\begin{aligned}  \sum_{k=1}^n(-1)^{k+1}\frac{1}{k}\binom{n}{k}&=\sum_{k=1}^n(-1)^{k+1}\left(\sum_{j=0}^{n-k}\frac{1}{n-j}\binom{n-j}{k}\right)\\  &=\sum_{j=0}^{n-1}\sum_{k=1}^{n-j}(-1)^{k+1}\frac{1}{n-j}\binom{n-j}{k}.\end{aligned}

i=n-j。代入上式,

\displaystyle  \sum_{i=1}^{n}\sum_{k=1}^{i}(-1)^{k+1}\frac{1}{i}\binom{i}{k}=\sum_{i=1}^n\frac{1}{i}\left(\sum_{k=1}^i(-1)^{k+1}\binom{i}{k}\right)=\sum_{i=1}^n\frac{1}{i}

請讀者自行證明 \sum_{k=1}^i(-1)^{k+1}\binom{i}{k}=1

 
最後我們補充一個運用微積分的計算方法。考慮

\displaystyle  (1-x)^n=\binom{n}{0}-\binom{n}{1}x+\binom{n}{2}x^2-\cdots+(-1)^{n}\binom{n}{n}x^{n}

\displaystyle  1-(1-x)^n=\binom{n}{1}x-\binom{n}{2}x^2+\binom{n}{3}x^3-\cdots+(-1)^{n+1}\binom{n}{n}x^{n}

上式除以 x

\displaystyle  \frac{1-(1-x)^n}{x}=\binom{n}{1}-\binom{n}{2}x+\binom{n}{3}x^2-\cdots+(-1)^{n+1}\binom{n}{n}x^{n-1}

等號兩邊從 01 積分,可得

\displaystyle  \int_{0}^1\frac{1-(1-x)^n}{x}dx=\binom{n}{1}-\frac{1}{2}\binom{n}{2}+\frac{1}{3}\binom{n}{3}-\cdots+(-1)^{n+1}\frac{1}{n}\binom{n}{n}

注意,上式等號右邊即為所求。利用變數變換積分等號左邊,令 y=1-x,即得

\displaystyle\begin{aligned}  \int_{0}^1\frac{1-(1-x)^n}{x}dx&=\int_1^0\frac{1-y^n}{1-y}(-dy)\\  &=\int_0^1(1+y+\cdots+y^{n-1})dy\\  &=\left.\left(y+\frac{1}{2}y^2+\cdots+\frac{1}{n}y^n\right)\right|_0^1\\  &=1+\frac{1}{2}+\cdots+\frac{1}{n}.\end{aligned}

 
參考來源:
[1] Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 2nd edition, 1973.

Advertisements
This entry was posted in 特別主題 and tagged , , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s