組合數學（二） 基本計數

　　高中的排列組合沒有意外的話，都是在處理組合計數的（Enumerative combinatorics）。組合計數底下又有排列（Permutation）、組合（Combination）以及分割（Partition），而組合計數本身就是找出這些可能形式（Possible Pattern）的數量。

　　為了明確界定我們的分析對象，我們要引進集合（Set）。一個集合是由其元素（Element）組成，一個集合內部的元素又可以自行組成子集（Subset）。集合大多是由大寫字母代表，用大括號表明內部的元素，並用豎線包住字母表示集合的元素數量。

　　接著就是本篇文章的第一個原理：若一組集合其中兩兩的交集（Intersection）為空集合（Null set），則元素數量相加的結果為這組集合的聯集（Union）的元素數量。也就是：

　　這個原理被稱作「加法原理」（Addition principle），用教科書的話來講就是「不可能同時發生的事情 A1、A2、A3......各有達成的方法 m1、m2、m3......種，則事件中至少有一發生的方法數為 m1 + m2 + m3 +......」。比如說 x y 皆為正整數時 2x + 3y ≦ 11 的所有可能情況：

1. x = 1, y = 1, 2x + 3y = 5
2. x = 1, y = 2, 2x + 3y = 8
3. x = 1, y = 3, 2x + 3y = 11
4. x = 2, y = 1, 2x + 3y = 7
5. x = 2, y = 2, 2x + 3y = 10
6. x = 3, y = 1, 2x + 3y = 9
7. x = 4, y = 1, 2x + 3y = 11

　　或者我們也可以 Mi 代表 2x + 3y = i 時 x 和 y 的解的集合， mi 代表其解的數量，如 m5 = 1（x = 1, y = 1），m11 = 2。2x + 3y 不可能同時為兩個數值，故根據加法原理，2x + 3y ≦ 11 會發生（2x + 3y 為 0 或 1 或......）的情況有 m5 + m7 + m8 + m9 + m10 + m11 = 1 + 1 + 1 + 1 + 1 + 2 = 7。第二個原理是：一組集合其元素數量相乘的結果為這組集合的笛卡爾積（Cartesian product）的元素數量。

　　其中 ×Si 為 S1×S2×S3×... 的縮寫。這個原理被稱作「乘法原理」（Multiplication principle）。笛卡爾積指的是集合的元素的所有可能組合，結果也是個集合。比如：

　　笛卡爾積並沒有交換律，也就是對調笛卡爾積中的兩個集合會產生一個元素數量相同但是元素（也就是原集合的元素的組合）和原來的是相反的。從上面的例子也可以看出 6 （笛卡爾積的元素數量） = 2 × 3。用教科書的說法就是「某一件事有 n 個步驟，第 i 個步驟有 ki 個方法，則完成此件事有 k1 × k2 × ..... 種方法。」前一章的飲品問題就是乘法原理的應用。當然，很多問題不只是單單地使用上面兩種原理的其中一種，而是同時用上，並且搭配其他如排列（P）等等。

　　在我們結束基本計數的章節前，還有一個東西是值得一提的—–惡名昭彰的錯排列（Derangement）。講白了，錯排列就是排容原理（Exclusion-inclusion principle）的特例。雖然號稱「排容」，事實上他就只是個求聯集的公式罷了：

　　在只有兩個集合的情況下：

　　真的要講到錯排列的話還有一些東西要講，這章就到這邊就可以了。