二項式係數與組合問題

本文的閱讀等級:初級

在組合數學,從包含 n 個元素的集合中選取 k 個元素的組合數 (不考慮次序),記為 \binom{n}{k},稱為二項式係數 (binomial coefficient)。我們先推導 \binom{n}{k} 的計算公式。設想有 n 個人在排隊買電影票,我們可以從 n 個人中選一人排在第一個位置,再從剩下的 n-1 個人裡選一人排在第二個位置,餘此類推,共有 n\cdot(n-1)\cdots 2\cdot 1=n! 種排列方式。再考慮第二種算法。電影院為鼓勵大眾及早排隊購票,特意準備了 k 張椅子,0\le k\le n,供給排在最前面的 k 個人歇坐。針對這個情況,從 n 個人中選取 k 個人進入歇坐區有 \binom{n}{k} 種方式,歇坐區內的 k 個人有 k! 種排列方式,歇坐區外的 n-k 個人有 (n-k)! 種排列方式,因此 n 個人排隊共有 \binom{n}{k}k!(n-k)! 種排列方式。合併上面兩個結果,即得

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

並定義邊界條件 \binom{n}{0}=\binom{n}{n}=1。根據對稱性,\binom{n}{k}=\binom{n}{n-k}

 
問題1:你邀請 6 位好友參加生日宴會,至少有一人出席生日宴會的來賓組合共有多少種?

因為至少有一個人出席派對,出席來賓的組合方式有

\displaystyle \binom{6}{1}+\binom{6}{2}+\binom{6}{3}+\binom{6}{4}+\binom{6}{5}+\binom{6}{6}=6+15+20+15+6+1=63

 
問題2:投擲一枚公正硬幣 6 次,出現至少一次正面的機率 (概率) 是多少?

出現 6 次反面的機率是 1/2^6,所以出現至少一次正面的機率是 1-1/2^6=63/64

 
表面上,問題1是組合問題,問題2是機率問題,但它們有相同的本質。某一位來賓出席與否對應於某次投擲硬幣出現正面與否,排除無人出席的情況,問題1的答案其實就是 2^6-1=63。舉凡問題涉及選取或捨棄有限集合的元素,這類問題的本質即為二項式係數。

 
二項式係數可由遞歸關係算得。若 n 固定,

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

上式說明 \binom{n}{k} 的最大值發生於鄰近 \frac{n-k}{k+1}\approx 1k 值,也就是當 k\approx \frac{n-1}{2}。若 k 固定,

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

二項式係數之名源於二項式定理,即下式:

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

其中 n 是非負整數。因為

\displaystyle    (a+b)^n=\underbrace{(a+b)(a+b)\cdots(a+b)}_{n}

乘開後每一項的形式為 a^{n-k}b^k0\le k\le n。對於特定 ka^{n-k}b^k 的係數等於從 n 個相同因式 (a+b) 選取 kb 的組合數 \binom{n}{k}。將 a=1b=t 代入二項式定理,可得

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

其中 t^k 的係數為 \binom{n}{k}。因此,(1+t)^n 稱為二項式係數的普通母函數或生成函數 (ordinary generating function)。寫出

\displaystyle (1+t)^n=(1+t)(1+t)^{n-1}

等號兩邊套用二項式定理,

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

比較等號兩邊 t^k 的係數,可得下列公式:

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

稱為帕斯卡 (Pascal) 法則。下面提供另一個論證:令 \Psi 表示 n 個元素構成的集合,設 x\in\Psi,由 \Psi 中選取 k 個元素可分開兩種情況討論:如果不取 x,則必須從 \Psi\setminus\{x\} 選取 k 個元素,組合數為 \binom{n-1}{k};如果選取 x,則還要從 \Psi\setminus\{x\} 取其餘 (k-1) 個元素,組合數為 \binom{n-1}{k-1}

 
帕斯卡三角形是帕斯卡法則的一種三角陣列排序,前面幾列 (row) 如下:

\begin{array}{ccccccccccccc}\displaystyle &&& &&& \binom{0}{0}&&&&&&\\ &&&&& \binom{1}{0}  & &  \binom{1}{1} &&&&&\\ &&&& \binom{2}{0}  & & \binom{2}{1}  & &  \binom{2}{2} &&&&\\ &&&\binom{3}{0} && \binom{3}{1} && \binom{3}{2}&& \binom{3}{3} &&&\\ &&\binom{4}{0}&& \binom{4}{1}&&\binom{4}{2}&&\binom{4}{3}&&\binom{4}{4}&&\\ &\binom{5}{0}&&\binom{5}{1}&&\binom{5}{2}&&\binom{5}{3}&&\binom{5}{4}&&\binom{5}{5}&\\ \binom{6}{0}&&\binom{6}{1}&&\binom{6}{2}&&\binom{6}{3}&&\binom{6}{4}&&\binom{6}{5}&&\binom{6}{6} \end{array}

實際數值如下:

\begin{array}{ccccccccccccc} &&& &&& 1&&&&&&\\ &&&&& 1  & &  1 &&&&&\\ &&&& 1  & & 2  & &  1 &&&&\\ &&&1 && 3 && 3&& 1 &&&\\ &&1&& 4&&6&&4&&1&&\\ &1&&5&&10&&10&&5&&1&\\ 1&&6&&15&&20&&15&&6&&1 \end{array}

 
觀察發現帕斯卡三角形各列的數字和依序是 1, 2, 4, 8, 16, 32, 64。這個現象要如何解釋?利用母函數可以推得二項式係數的一些有用的公式。設 t=1,可得

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

直白地說,從包含 n 個元素的集合選取,所有組合數 (二項式係數) 之和等於 2^n (如果我們知道這個事實,便能立刻回答問題1)。設 t=-1,可得

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

這表示對於任一 n,奇數指標的二項式係數和等於偶數指標的二項式係數和,即 2^{n-1}。譬如,當 n=61+15+15+1=6+20+6=2^5。計算母函數對 t 的導數,可得

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

代入 t=1,即有

\displaystyle n2^{n-1}=\sum_{k=1}^nk\binom{n}{k}

通過設計包含變數 t 的二項式,微分或積分,並以適當的數值代入 t,我們可以導出許多二項式恆等式,困難之處在於究竟該怎麼做才能得到我們希望的公式。有興趣深入了解讀者請參閱“二項式係數公式”。

 
問題3:在撲克牌遊戲中,為甚麼五張牌型的鐵扇 (四條,four of a kind) 擊敗葫蘆 (夫佬,full house)?

鐵扇的牌型,例如 3♠ 3♥ 3♦ 3♣ 8♥,可由 13 種不同的數字組成四張同點數牌,第五張牌有 52-4=48 種可能,所有可能的鐵扇牌型數是 13\cdot 48=624。因此,手上五張牌是鐵扇的機率為 624/\binom{52}{5}\doteq 0.00024。葫蘆的牌型,例如 3♠ 3♥ 3♦ 8♣ 8♥,可由 13 種不同數字的四張同點數牌選出三張組成,接著由 12 種數字的四張同點數牌選出二張組成,可能的牌型數為 13\cdot\binom{4}{3}\cdot 12\cdot\binom{4}{2}=3,744。因此,手上五張牌是葫蘆的機率為 3,744/\binom{52}{5}\doteq 0.0014,等於鐵扇的 6 倍。

 
上面這個問題的算法直覺簡單,但很多組合問題不像代數問題有比較固定的套路或解法。因為這個緣故,往往我們要憑個人想像,編織出一個較容易切入或推理的等價問題。舉個誇張的例子,如果一個盲人想知道森林裡有多少顆樹,我們可以在每一顆樹上放一隻小貓。盲人行經每顆樹時,導盲犬對著樹上的小貓叫一聲 (為避免重複計算,小貓叫了一聲後,盲人的魔法手杖立刻就將牠變成啞巴貓)。下面列舉一些解答為二項式係數的組合問題。

 
問題4:包含 5130 的字符串 (string) 共有多少個?

字符集 \{1,1,1,1,1,0,0,0\} 稱為一個多重集 (multiset),或記為 \{(1,5),(0,3)\},其中 1 的重數 (multiplicity) 是 50 的重數是 3。多重集的元素數,包含相重元素,稱為基數 (cardinal number),此例多重集的基數是 8。將多重集 \{(1,1,1,1,1,0,0,0\} 的字符置於下面的 8 個槽 (每個槽放一個字符),即可排成一字符串:

\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup

多重集 \{1,1,1,1,1,0,0,0\} 可組成的字符串總數等於從 8 個槽 (基數) 選取 5 個槽置放 1 (或選取 3 個槽置放 0) 的組合數,\binom{8}{5}=56。另外,多重集 \{(1,1,1,1,1,0,0,0\} 組成的字符串也可當作不盡相異物排列。設想令 8 個字符按直線排列 (共有 8! 種方式),扣除重複計算的 51 的排列 (共有 5! 種方式) 與 30 的排列 (共有 3! 種方式),可得 \frac{8!}{5!3!}=\binom{8}{5} 種排列方式。所以,包含 n1k0 的字符串共有 \binom{n+k}{n}=\binom{n+k}{k} 個。

 
問題5:包含 5130,且沒有兩個 0 相鄰的字符串共有多少個?

根據問題的限制,我們在相鄰字符 1 之間加入一個槽,同時在頭尾也加入一槽,如下:

\sqcup 1 \sqcup 1\sqcup 1\sqcup 1\sqcup 1\sqcup

5+1=6 個槽選取 3 個置放 0 的組合數即為所求,答案是 \binom{6}{3}=20。所以,包含 n1k0,且沒有兩個 0 相鄰的字符串共有 \binom{n+1}{k} 個。根據對稱性,沒有兩個 1 相鄰的字符串共有 \binom{k+1}{n} 個。

 
問題6:你有 10 張相同樣式的遊戲卡要分給 6 位好友,共有幾種方法?

等價的問題是投擲一顆六面骰子 10 次,共有幾種結果 (不考慮點數出現的次序)?不定方程 x_1+x_2+\cdots+x_6=10 共有多少非負整數解?或者,你從裝了無窮多顆包含 6 種不同顏色球的大桶子挑出 10 顆球,共有多少種組合?這個問題稱為重複組合 (combination with repetition)。舉一例說明,我們用有序數組 (2,3,0,1,4,0) 代表投擲骰子 10 次,點數 1,2,3,4,5,6 出現的次數分別為 2,3,0,1,4,0,圖示如下:

\bullet\bullet\vert \bullet\bullet\bullet\vert ~~\vert\bullet\vert \bullet\bullet\bullet\bullet\vert

圖中 5 個線段 \vert 表示相鄰擲點數 (以 \bullet 表示) 之間的分割線。上圖提示我們投擲一顆六面骰子 10 次的結果對應多重集 \{(\bullet,10),(\vert,5)\} 組成的字符串,由問題4可知所求為 \binom{15}{10}=3,003。所以,k 個相同物件分成 n 組共有 \binom{n+k-1}{k}=\binom{n+k-1}{n-1} 種方法。

 
問題7:你有 10 張相同樣式的遊戲卡要分給 6 位好友,每人至少分得一張,共有幾種方法?

這個問題也可以表示為不定方程 x_1+x_2+\cdots+x_6=10x_i\ge 1i=1,2,\ldots,6,共有多少整數解?根據題意,每個人先發一張卡以使 x_i\ge 1,剩下的 4 張卡再分給 6 個人,套用問題6的結論,答案是 \binom{6+4-1}{4}=\binom{9}{4}=126。因此,k 個相同物件分成 n 組,每組至少分得一個物件,共有 \binom{n+k-n-1}{n-1}=\binom{k-1}{n-1} 種方法。

 
問題8:不定方程 x_1+x_2+x_3=5 滿足 x_1\ge 0x_2\ge 1x_3\ge -2,有多少整數解?

利用變數變換,設 x'_2=x_2-1x'_3=x_3+2,代入不定方程可得等價表達式 x_1+x'_2+x'_3=6,共有 \binom{3+6-1}{6}=\binom{8}{6}=28 組非負整數解。

 
問題9:不等式 x_1+x_2+x_3\le 5 有多少非負整數解?

最直接的想法是將 x_1+x_2+x_3\le 5 區分為 6 種情況 x_1+x_2+x_3=pp=0,1,\ldots,5,每一種情況有 \binom{3+p-1}{p} 個解,加總如下:

\displaystyle \binom{2}{0}+\binom{3}{1}+\binom{4}{2}+\binom{5}{3}+\binom{6}{4}+\binom{7}{5}=1+3+6+10+15+21=56

觀察帕斯卡三角形可見序列 1,3,6,10,15 出現於第三對角線上,暗示我們上式應可進一步化簡。下面的等式稱為求和公式 (見“二項式係數公式”):

\displaystyle \binom{2}{0}+\binom{3}{1}+\binom{4}{2}+\binom{5}{3}+\binom{6}{4}+\binom{7}{5}=\binom{8}{5}

沿用問題6的思維很容易解釋求和公式的涵義。考慮不定方程 x_1+x_2+x_3+x_4=5,引入非負整數 x_4=5-p 可使 x_1+x_2+x_3\le 5,故前者與後者有相同的非負整數解數,答案是 \binom{4+5-1}{5}=\binom{8}{5}=56。所以,不等式 x_1+x_2+\cdots+x_n\le k 共有 \binom{n+k}{k} 組非負整數解。

 
上面所列舉的問題不具組合結構。在組合數學中,許多組合結構可用卡塔蘭數 (Catalan number) 來計數,如下:

\displaystyle C_n=\frac{1}{n+1}\binom{2n}{n},~~n\ge 1

例如,包含 n+1 個終端頂點 (樹葉) 的二元樹 (binary tree) 數等於 C_n,計算 n 個矩陣乘積的所有括號方式為 C_n,讀者可參閱“矩陣鏈乘積的最佳計算順序”。

This entry was posted in 機率統計 and tagged , , , . Bookmark the permalink.

發表迴響

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

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s