前言

參考資料

  1. The Art of Computer Programming, Volume 1, Chapter, 1.2.6 Binomial Coefficient
  2. 線代啟示錄-二項式係數公式

這篇主要是要自己來go through一次這整章的推演過程。

正文

Equation #0

\binom{n}{r} = \frac{n!}{r!(n-r)!}

Equation #1

\binom{n}{r} = \binom{n}{n-r}

這個可以很直觀的理解為,從n項裡面選了r項物品,等價於從n項裡面選了n-r項"沒被選上"的物品,所以不證明。

Equation #2

\binom{n}{r} = \frac{n}{r}\binom{n-1}{r-1}
證明
\binom{n}{r} = \frac{n!}{r!(n-r)!}\\
\, \\
\binom{n}{r} = \frac{n}{k}\frac{(n-1)!}{(r-1)!(n-r)!}\\
\, \\
\because \binom{n-1}{r-1} = \frac{(n-1)!}{(r-1)!(n-r)!}
\quad
\therefore \binom{n}{r} = \frac{n!}{r!(n-r)!}\\
延伸
Equation #2.1
(n-r)\binom{n}{r} = n\binom{n-1}{r}
證明
\binom{n}{r} = \binom{n}{n-r}\quad by\quad Eq.1\\
\,\\
\binom{n}{r} = \frac{n}{n-r}\binom{n-1}{n-r-1}\quad by\quad Eq.2\\
\,\\
\binom{n}{r} = \frac{n}{n-r}\binom{n-1}{r}\quad by\quad Eq.1\\
\,\\
(n-r)\binom{n}{r}=n\binom{n-1}{r}

Equation #3

\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}
證明
r\binom{n}{r} = n\binom{n-1}{r-1}\quad by\quad Eq.2\quad (1)\\
\,\\
(n-r)\binom{n}{r}=n\binom{n-1}{r}\quad by\quad Eq.2.1\quad (2)\\
\,\\
n\binom{n}{r}=n\binom{n-1}{r-1}+n\binom{n-1}{r}\quad\quad (1)+(2)\\
\,\\
\binom{n}{r}=\binom{n-1}{r-1}+\binom{n-1}{r}\quad times\quad\frac{1}{n}\quad to\quad both\quad side
延伸

利用Equation #3可以很容易的利用Top-down的方式導出很多有用的公式,難的是遇到展開的式子要怎麼把它和組合做連結,以下證明兩個式子當作範例。

Equation #3.1
\binom{r+n+1}{n} = \sum_{k=0}^{n}\binom{r+k}{k}
證明

其實就是一直用Equation #3展開

\binom{r+n+1}{n} = \binom{r+n}{n}+\binom{r+n}{n-1}\\
\,\\
\binom{r+n+1}{n} = \binom{r+n}{n}+\binom{r+n-1}{n-1}+\binom{r+n-1}{n-2}\\
\,\\
\binom{r+n+1}{n} = \binom{r+n}{n}+\binom{r+n-1}{n-1}+\binom{r+n-2}{n-2}+\binom{r+n-2}{n-3}\\
\,\\
...\\
\,\\
\binom{r+n+1}{n} = \binom{r+n}{n}+\binom{r+n-1}{n-1}+...+\binom{r}{0}\\

如果後面有展開到負的下項,根據定義該項值為零可以直接消除。

下面這個式子需要用到上面的來做推導。

Equation #3.1
\binom{n+1}{m+1} = \sum_{k=0}^{n}\binom{k}{m}
證明

可以看出總和中k<m的部分會是0。

\sum_{k=0}^{n}\binom{k}{m}=\sum_{k=m}^{n}\binom{k}{m}\\
\,\\
\sum_{k=m}^{n}\binom{k}{m}=\binom{m}{m} + \binom{m+1}{m} + ... + \binom{n}{m}\\
\,\\
\sum_{k=m}^{n}\binom{k}{m}=\binom{m}{0} + \binom{m+1}{1} + ... + \binom{n}{n-m}\quad by\quad Eq.1\\
\,\\
rewrite,\quad\sum_{k=0}^{n-m}\binom{m+k}{k}=\binom{m}{0} + \binom{m+1}{1} + ... + \binom{n}{n-m}\\
\,\\
\sum_{k=0}^{n-m}\binom{m+k}{k}=\binom{m+(n-m)+1}{n-m+1}=\binom{n+1}{n-m}\quad by\quad Eq.3.1\\
\,\\
\binom{n+1}{n-m}=\binom{n+1}{m+1}\quad by\quad Eq.1\\

Equation #4

二項式定理

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

這個要證明的話,我也只會用歸納法,所以不證了。

Equation #5

\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k}
證明

想不到用階乘以外的證法,想到後補上,如果有人有其他證明也懇請提供。

Equation #6

\sum_{k=0}^{n}\binom{r}{k}\binom{p}{n-k}=\binom{r+p}{n}
證明

利用Equation #4把右式展開成左式,待補。

最後修改日期: 4 12 月 2019

留言

撰寫回覆或留言

發佈留言必須填寫的電子郵件地址不會公開。