加法原理，乘法原理（Addition Principle and Multiplication Principle）

加法原理，乘法原理（Addition Principle and Multiplication Principle）
國立高雄大學應用數學系游森棚教授/國立高雄大學應用數學系游森棚副教授責任編輯

計數問題千奇百怪，各式各樣。數學的任何一個學門，都可以跟計數沾上一點邊。也因此，很難對計數問題作歸類。但是，處理這樣形形色色的問題，根本的基礎原理卻就只有五個：

加法原理，乘法原理，對應原理，Fubini原理，排容原理

這五個其貌不揚的原理是計數組合學理論的基石，善用這些原理，可以解決非常複雜的問題，這也是計數組合迷人之處。本文介紹加法原理和乘法原理。

加法原理

高中數學課本是這樣講加法原理的：台北到高雄走陸路有 \(4\) 條路線，走水路有 \(2\) 條路線，走空運有 \(3\) 條路線。請問台北到高雄一共有幾條路線？答案是 \(4+2+3=9\)

一般來說，有如下的加法原理：

如果要完成一件事有 \(k\) 類方式，第一類方式有 \(n_1\) 個方法，第二類方式有 \(n_2\) 個方法，…，第 \(k\) 類方式有 \(n_k\) 個方法。
則完成這件事有 \(n_1+n_2+\mbox{…}+n_k\) 個方法。

多半學生對這個例題根本嗤之以鼻－這太瞧不起人了；而老師也鮮少闡釋加法原理所要傳達的重要訊息：

加法原理的精神在於“分類”

也就是說，如果要計數的集合可以分類成互不相交的若干部分，則分別把每個部分算出後相加即可。用數學的語言來說，

加法原理：設 \(S={\bigcup}^t_{i=1}S_i\)，其中 \(Si\bigcap{Sj}=\phi\)，則 \(|S|={\sum}^t_{i=1}|Si|\)

加法原理也是導出遞迴關係式的基礎。例如二項式係數：令 \(a_{n,k}\) 表示從 \(n\) 個數中（不妨假設是 \(1,2,\mbox{…},n\)）選出 \(k\) 個數的組合數。則所有的方法可以分成兩類：\(1\) 被選到，以及 \(1\) 沒被選到，這兩類互不相交。

如果 \(1\) 被選到，剩下 \(n-1\) 個數還要選 \(k-1\) 個數，有 \(a_{n-1,k-1}\) 個方法。如果 \(1\) 沒被選到，剩下 \(n-1\) 個數還要選 \(k\) 個數，有 \(a_{n-1,k}\) 個方法。因此得到遞迴式

\(a_{n,k}=a_{n-1,k-1}+a_{n-1,k}\)

再由初始值 \(a_{n,0}=1\) 及 \(a_{n,n}=1\)，馬上就可以把整個巴斯卡三角形畫出來了。

“分類”的思想不只是排列組合，在數學的任何領域都是重要的。試圖將某個抽象結構完整分類，是許多領域重要的目標。

乘法原理

高中數學課本是這樣講乘法原理的：台北到台中有 \(4\) 條路線，台中到高雄有 \(3\) 條路線。請問台北到高雄一共有幾條路線？答案是 \(4\times{3}=12\)

一般來說,有如下的乘法原理：

如果要完成一件事，依次要進行 \(k\) 個步驟；做完第一個步驟有 \(n_1\) 個方法，做完第二個步驟有 \(n_2\) 個方法，\(\mbox{…}\)，做第 \(k\) 個步驟有 \(n_k\) 種方法。
則完成這件事有 \(n_1\cdot{n_2}\cdot\mbox{…}\cdot{n_k}\) 種方法。

同樣地，乘法原理所要傳達的重要訊息是：

乘法原理的精神在於“各個擊破”

也就是說，如果要計數的集合可以分類成一連串的單線進行的步驟，則分別把每個步驟方法數算出後相乘即可。用數學的語言來說，

乘法原理：設 \(S={\prod}^t_{i=1}S_i\)，則 \(|S|={\prod}^t_{i=1}|S_i|\)

這裡 \(S:={\prod}^t_{i=1}S_i=S_1\times{S_2}\times\mbox{…}\times{S_t}=\{(a_1,\mbox{…},a_t):a_i\in{S_i},1\leq{i}\leq{t}\}\) 為集合的乘積（Cartesian product）.

一個簡單而重要的例子來自資訊科學裡的“形式語言(formal language)”領域。在這個研究抽象語言的領域裡，一開始有一些可用的字母，字母所成的集合 \(S\) 稱為這個語言的字母集(alphabet)，一些字母可以形成一個單字的單字有多少？顯然，第一個位置有 \(a\) 種方法，第二個為置有 \(a\) 種方法，….，因此由乘法原理一共有 \(a\times{a}\mbox{…}\times{a}= a^n\) 個字。

當然有些單字也許在這個語言中沒意義，但這是另外一個層面的問題了。為什麼資訊學家要研究抽象語言？注意到 \(S={0,1}\) 時，這個語言只有 \(0\) 與 \(1\)，這正是電腦的世界。\(S=\{A,T,G,C\}\) 時，這個語言就是 \(DNA\) 解碼，全世界生物學家都想知道的生命秘密。在這裡，組合學與生物學和資訊科學有了交集。

配合加法原理與乘法原理，可以解決高中數學排列組合中絕大部分的問題。給一個有意義的例子：令 \(n={p}^{a_1}_1{p}^{a_2}_2\mbox{…}{p}^{a_t}_t\) 是標準質因數分解，問 \(n\) 有多少正因數？這是高一學生人人會背的公式，但是要用到加法原理與乘法原理才能解釋：

因為 \(n\) 的正因數必形如 \(n={p}^{b_1}_1\mbox{…}{p}^{b_t}_t\)，其中 \(0\leq{b_i}\leq{a_i}\)。因此 \(b_i\) 有 \((a_i+1)\) 個選法（這用到加法原理）。故 \(n\) 一共有 \((a_1+1)(a_2+1)\mbox{…}(a_t+1)\) 個正因數（這個用到乘法原理）。

在下一篇文章中，我們談另外幾個原理。