基本計數（三） 進階計數

　　進階計數建立於基礎計數之上，將引入集合的計數原理帶入更抽象的境界。

　　話是這麼說，其實裡面不完全是陌生的面孔。不過在那之前，倒是有些事情要先說清楚。上一個章節中的計數都僅侷限於集合中，在這一個章節中，我們要把對象從集合中的元素轉到集合間的映射關係。基本計數的問題大多是處理事件的合併，而進階計數的則是集合元素的選取，所以用映射函數處理這類問題也是合理的。記住，進階計數算的是在給定條件下在兩集合間映射的函數 f 有多少個。

　　假設現在有 X 和 Y 兩個集合，並規定函數 f: X → Y。這個函數可以是任意的（Arbitrary）、單射的（Injective）或滿射的（Surjective）。單射函數要求 X 內的每一元素都映射到 Y 內不同的元素；滿射函數則要求 Y 中的每一元素都有至少一個在 X 中對應的元素。設 X 有 x 個元素， Y 有 y 個，則計數的公式是：

　　其中  就是大家熟悉的 C，或稱二項式係數（Binomial coefficient）；而  是司特靈第二類數（Stirling number of the second kind）。舉列來說，設 X = {1, 2}，Y = {A, B, C, D}，f 為單射，有以下幾種映射方式：

1. 1 → A, 2 → B
2. 1 → A, 2 → C
3. 1 → A, 2 → D
4. 1 → B, 2 → A
5. 1 → B, 2 → C
6. 1 → B, 2 → D
7. 1 → C, 2 → A
8. 1 → C, 2 → B
9. 1 → C, 2 → D
10. 1 → D, 2 → A
11. 1 → D, 2 → B
12. 1 → D, 2 → C

不多不少剛好就是排列 。反過來看，單射 f: X → Y 也可以看成是從 Y 中取元素排列後放到 X 中，被選到的元素對應到原本的集合裡的元素。若是這個 f 是任意的，則 X 中的元素可以對應到 Y 中的任一元素，變成所謂的重複排列。在上面的例子中，X 的元素（1 和 2）是有分別的，萬一我們今天不理會其中的差異，把兩者視作相同呢？

1. X = {A, B}
2. X = {A, C}
3. X = {A, D}
4. X = {B, C}
5. X = {B, D}
6. X = {C, D}

也就是原本的 1 → A, 2 → B 和 1 → B, 2 → A 被我們視作是同樣的一組答案。結果就只剩六組了。這樣子的動作被稱「up to the permutation of X」，以 f ⸰ Sx 表示。事實上這個「up to」 很難翻成中文，粗略地說就是「忽略其中的差異，視為等價」。X 中的元素若忽略其中的排列的話，f 的數量的確是會縮減到剩下 6 組。要是我們把這個條件「忽略 X 的排列」加到 f 上的話：

　　原本的排列變成了組合，重複排列也變成了重複組合（H）。至於滿射 f ⸰ Sx 的用處看似一時間很難想出來，其實是有的。考慮 x = z1 + z2 + ... + zy 的正整數解，若設 x = 5，y = 3，透過窮舉：

1. 5 = 1 + 1 + 3
2. 5 = 1 + 3 + 1
3. 5 = 3 + 1 + 1
4. 5 = 1 + 2 + 2
5. 5 = 2 + 1 + 2
6. 5 = 2 + 2 + 1

的確是  沒錯。現在再考慮「忽略 Y 的排列」，也就是「up to the permutation of Y」。沿用 X = {1, 2}，Y = {A, B, C, D} 的例子來說的話，就會變成「X 的 1 和 2 對應到一堆相同的東西」，只剩下一種取法。故我們有：

而滿射的 Sy ⸰ f 有一個特殊用途：將集合 X 分割成 y 個非空集合，這正是滿射的性質。若是將這些 y 個非空集合排列，那就會回到滿射的 f 了。分割的結果數可用司特靈第二類數來描述，他有條公式是長這樣的：

不過你大概一輩子也用不到這條麻煩到不行的式子，我們有更快的方式：

不，我指的不是查表，這張表得要由你自己來建構。有幾個規則可以讓你在一分鐘之內就把整張表給寫出來：對角線上的數字一定是 1、第一行的數字除了第一個是 1 以外其餘都是 0、第二行的數字全都是 1、右上角的部分沒有數字。抓一個數字，乘上其所在的行數，加上其左邊的數字，就是其正下方的數字了。

舉列來說，設 集合 X = {A, B, C, D}，要分割成二個非空集合：

1. {A, B, C}, {D}
2. {A, B, D}, {C}
3. {A, C, D}, {B}
4. {B, C, D}, {A}
5. {A, B}, {C, D}
6. {A, C}, {B, D}
7. {A, D}, {B, C}

的確是  無誤。至於任意的 Sy ⸰ f 則是把不分割到分割成 y 個全都考慮過一遍，因為沒有條件限制 Y 中的所有元素都一定要在 X 中有對應的元素。最後要做的事是同時忽略 X 和 Y 的排列：

到了這個地步已經是在考慮「如何把一堆相同的東西分堆」了。若是 Sy ⸰ f ⸰ Sx，則是「一個正整數 x 拆成 y 個數字相加時有幾種分拆法」，比如 5 = 1 + 4 = 2 + 3 就是 p2(5) = 2。以上三種 f 的映射條件，加上四種 X 和 Y 的排列考慮，就是十二道計數方法（Twelvefold way），概念最早由美裔數學家羅塔（Rota，1932 - 1999）提出。你必需要注意的是十二道計數方法只是將組合計數中常見的問題有系統地統整，並不是說 f 單射就可以推導出這裡要用 P。這些被統整在一塊的問題本質上可以集合和函數映射關係來描述，因此就將他們系統化。

基本計數感覺被遺忘了。許多的應用問題是混搭著基本計數和十二道計數方法的。下一章我們終於要來玩真的了。