至此筆者已討論了《點算的奧秘：分配問題》表2上的四大「點算組合學」問題(「排列」、「組合」、「集合劃分」和「整數分割」問題)中的三個的「母函數」，本節要介紹餘下一種問題－「集合劃分」問題的「母函數」。筆者在《點算的奧秘：集合劃分問題》中曾介紹多種「集合劃分」問題，本節將只集中討論「不容許空集的集合劃分」問題。此外，雖然本網頁的主旨是推導「集合(無序)劃分」問題的「母函數」，但由於「集合(無序)劃分」問題與「集合有序劃分」問題有密切關係，本網頁亦會經常借助「集合有序劃分」問題的「母函數」(註1)。
在上述四大「點算組合學」問題中，「集合劃分」問題較為特殊，因為這種問題在表達為「母函數」方面有較大的局限性。就筆者所知，只有部分「集合劃分」問題能容易地表達為「母函數」。我們先從最簡單的情況開始，即除了不容許空集外，沒有其他限制的「集合劃分」問題。
根據《點算的奧秘：集合劃分問題》，「不容許空集的集合(無序)劃分」問題與「不容許空集的集合有序劃分」問題的計算公式有以下關係：
上式就是上述網頁中的公式(3)。在上式中，P1(r, n)和D1(r, n)分別代表把r個元素劃歸n個非空(無序)子集以及把r個元素劃歸n個非空有序子集的「劃分」方案總數。由於「集合有序劃分」問題對應著「排列」問題(見註1)，因此「把r個元素劃歸n個非空有序子集」的問題便對應著「從n類物件中抽r個出來排列，其中每類物件都必須至少抽一個出來」的問題。根據《點算的奧秘：指數母函數》的最後部分，上述「排列」問題，亦即D1(r, n)的「指數母函數」是
| (x + x2/2! + ...)n | |
| = | (ex − 1)n (2) |
由於D1(r, n)就是上式展開式中xr / r!項的「系數」，我們應有以下等式：
把上式等號左、右端同時除以n!，並利用上面的公式(1)，便可得到
| (ex − 1)n / n! | = [Σ1 ≤ r < ∞ D1(r, n) xr / r!] / n! |
| = Σ1 ≤ r < ∞ [D1(r, n) / n!] xr / r! | |
| = Σ1 ≤ r < ∞ P1(r, n) xr / r! |
經過以上計算，我們便得到「求P1(r, n)的指數母函數」：
P1(r, n)就是上式展開式中xr / r!項的「系數」。
請注意上式其實就是把公式(2)除以n!的結果，此一結果之所以成立是因為有上面公式(1)所示的關係。其實我們還可以把公式(1)推廣到更一般的「集合劃分」問題，並且定義Pi(r, n)和Di(r, n)如下(註2)：
| Pi(r, n) | = 把r個元素劃歸n個(無序)子集並且規定每個(無序)子集含有最少i個元素的「劃分」方案總數 |
| Di(r, n) | = 把r個元素劃歸n個有序子集並且規定每個有序子集含有最少i個元素的「劃分」方案總數 |
請注意為使以上兩個定義有意義，我們必須有r ≥ in。容易看到，Pi(r, n)與Di(r, n)之間存在以下關係：
這是因為給定一個含有n個子集的「(無序)劃分」方案，我們只要把這n個子集進行「全排列」，便可得到相應的n!個「有序劃分」方案。舉例說，若r = 8，n = 3，i = 2，那麼{{1,2,3},{4,5,6},{7,8}}便是其中一個「(無序)劃分」方案，對應於這個方案，我們有以下3! = 6個「有序劃分」方案：
由於上述「(無序)劃分」方案共有P2(8, 3)個，每個都對應著3!個「有序劃分」方案，所以共有3! × P2(8, 3)個「有序劃分」方案，而這個數正等於D2(8, 3)。
現在我們利用公式(4)推導Pi(r, n)的「母函數」。根據《點算的奧秘：分配問題》，上述Di(r, n)等同於「從n類物件中抽r個出來排列，其中每類物件都必須至少抽i個出來」的問題，因此使用《點算的奧秘：指數母函數》中的概念以及ex的「馬克勞林展開式」，可以把Di(r, n)表達為以下的「指數母函數」：
| [xi/i! + xi+1/(i+1)! + ...]n | |
| = | [ex − 1 − x − x2/2! ... xi−1/(i−1)!]n |
由於Di(r, n)就是上式展開式中xr / r!項的「系數」，我們應有以下等式：
把上式等號左、右端同時除以n!，並利用上面的公式(4)，便可得到
| [ex − 1 − x − x2/2! ... xi−1/(i−1)!]n / n! | = [Σin ≤ r < ∞ Di(r, n) xr] / n! |
| = Σin ≤ r < ∞ [Di(r, n) / n!] xr / r! | |
| = Σin ≤ r < ∞ Pi(r, n) xr / r! |
經過以上計算，我們便得到「求Pi(r, n)的指數母函數」：
| [ex − 1 − x − x2/2! ... xi−1/(i−1)!] / n! | |
| = | [xi/i! + xi+1/(i+1)! + ...]n / n! (5) |
Pi(r, n)就是上式展開式中xr / r!項的「系數」。
當然我們還可以仿照《點算的奧秘：二元母函數》中介紹的方法推導上述問題的「二元指數母函數」。當上述問題中的n等於一個確定的值k時，相關的「一元指數母函數」為
當k的值變化時，上式便會隨之而變化。現在只要我們把上式乘以yk，並對k求和，便得到「求Pi(r, n)的二元指數母函數」：
Pi(r, n)就是上式展開式中xryn / r!項的「系數」。不過在實際應用上，使用公式(5)會更為簡單直接。
例題1：現要把8個元素劃歸3個(無序)子集，並規定每個子集至少須包含2個元素，問有多少種不同的「(無序)劃分」方案？
答1：把r = 8，n = 3，i = 2代入公式(5)，便得到求P2(8, 3)的「指數母函數」為
所求答案就是上式展開式中x8 / 8!項的「系數」。根據觀察，當我們從上面3個「括弧」中分別取出以下各項時，相乘便會得到x8項：x2/2!, x2/2!, x4/4!; x2/2!, x3/3!, x3/3!; x2/2!, x4/4!, x2/2!; x3/3!, x2/2!, x3/3!; x3/3!, x3/3!, x2/2!; x4/4!, x2/2!, x2/2!。把以上的項相乘並相加，然後除以3!，便得到
| [x8/(2!2!4!) + x8/(2!3!3!) + x8/(2!4!2!) + x8/(3!2!3!) + x8/(3!3!2!) + x8/(4!2!2!)] / 3! | |
| = | [(420 + 560 + 420 + 560 + 560 + 420)x8/8!] / 3! |
| = | 490x8/8! |
由此得知本題答案為490。□
在以上例題中，各個子集的元素個數被設定了「下限」。其實利用以上方法，我們還可以解決一些帶有特殊限制條件的「集合劃分」問題。
例題2：試推導以下問題的「指數母函數」：現要把r個元素劃歸n個(無序)子集，並規定每個子集須包含奇數個元素，問有多少種不同的「(無序)劃分」方案？求r = 7，n = 3時的答案。
答2：我們把上述「集合(無序)劃分」問題的答案稱為Po(r, n)(這裡o代表「奇數」Odd Number)，並把相關的「集合有序劃分」問題的答案稱為Do(r, n)，顯然Do(r, n) = n! × Po(r, n)。上述相關的「集合有序劃分」問題對應於以下「排列」問題：現要從n類物件中抽r個出來排列，並規定各類被抽出來的物件的數目須為奇數，問有多少種不同的「排列」方案？容易看到，上述「排列」問題的「指數母函數」為
由於上式展開式中xr / r!項的「系數」就是上述「排列」問題的答案，亦即Do(r, n)，我們應有以下等式：
把上式等號左、右端同時除以n!，並利用Do(r, n)與Po(r, n)的關係式，便可得到
| (x + x3/3! + x5/5! + ...)n / n! | = [Σ1 ≤ r < ∞ Do(r, n) xr] / n! |
| = Σ1 ≤ r < ∞ [Do(r, n) / n!] xr / r! | |
| = Σ1 ≤ r < ∞ Po(r, n) xr / r! |
以上演算顯示，Po(r, n)的「指數母函數」為
Po(r, n)就是上式展開式中xr / r!項的「系數」。
當r = 7，n = 3時，上述問題的「指數母函數」便成為
所求答案就是上式展開式中x7 / 7!項的「系數」。根據觀察，當我們從上面3個「括弧」中分別取出以下各項時，相乘便會得到x7項：x, x, x5/5!; x, x3/3!, x3/3!; x, x5/5!, x; x3/3!, x, x3/3!; x3/3!, x3/3!, x; x5/5!, x, x。把以上的項相乘並相加，然後除以3!，便得到
| [x7/5! + x7/(3!3!) + x7/(5!) + x7/(3!3!) + x7/(3!3!) + x7/(5!)] / 3! | |
| = | [(42 + 140 + 42 + 140 + 140 + 42)x7/7!] / 3! |
| = | 91x7/7! |
由此得知本題答案為91。□
以上的解題方法有一個重要限制，就是各個子集必須受著相同的限制條件(筆者把這種情況稱為「同質限制條件」Homogeneous Constraint)。如果各個子集的限制條件各有不同(筆者把這種情況稱為「異質限制條件」Heterogeneous Constraint)，則上述解題方法會帶來一定困難。試考慮以下「帶異質限制條件的集合劃分問題」：
| (A) | 現要把6個元素劃歸2個(無序)非空子集，並規定其中一個子集至少包含3個元素，另一個子集最多包含4個元素，問有多少種不同的「(無序)劃分」方案？ |
讀者可自行驗證，如果我們沿用以上的解題方法，把與上述問題相關的「集合有序劃分」問題表達為以下的「指數母函數」：
並從而推出上述問題的「指數母函數」為
則所得「答案」為20.5，但這是不可能的！究竟問題出在哪裡？造成上述錯誤的原因在於上面的算式(6)並不適合用來解答上題。算式(6)代表以下這個「集合有序劃分」問題：
| (B) | 現要把6個元素劃歸2個有序非空子集A1和A2，並規定A1至少包含3個元素，A2最多包含4個元素，問有多少種不同的「有序劃分」方案？ |
比較一下問題(A)和(B)，便會發現兩者的限制條件有很不同的表達形式。問題(A)的限制條件是「其中一個子集...，另一個子集...」。由於它沒有明確規定哪一個子集是「其中一個」，因此任何一個子集都可以是「至少包含3個元素」的那個子集。換句話說，兩個子集的角色可以對調。與此不同，問題(B)的限制條件明確規定了A1是「至少包含3個元素」的那個子集，A1和A2的角色不可對調。正是由於上述差異，這兩個問題的答案並不存在簡單的對應關係。例如，雖然{{1},{2,3,4,5,6}}是符合問題(A)限制條件的「(無序)劃分」方案，但是在對應著這個方案的兩個「有序劃分」方案：{1}-{2,3,4,5,6}和{2,3,4,5,6}-{1}中，只有後者符合問題(B)的限制條件。由此可見，(B)的答案不可能是(A)的答案的兩倍(利用算式(6)，可以求得(B)的答案為41，而(A)的正確答案是31)。
對於「帶同質限制條件的集合劃分」問題而言，上述錯誤卻並不存在。這是因為在「同質限制條件」下，各個子集的角色可以互相對調，即對於某個符合限制條件的「有序劃分」方案而言，把方案中的子集重新排序後，所得的新方案仍然符合有關限制條件。舉例說，前面例題2的限制條件為每個子集須包含奇數個元素，「有序劃分」方案{1,2,3}-{4,5,6}-{7}符合這個限制條件。當我們把這個方案中的3個子集重新排序後，所得的新方案(例如{4,5,6}-{1,2,3}-{7}、{1,2,3}-{7}-{4,5,6}等)仍然符合這個限制條件。因此符合該題限制條件的「有序劃分」方案總數必然是「(無序)劃分」方案總數的3!倍。以上討論解釋了為何本網頁介紹的「母函數」方法可用來解決「帶同質限制條件的集合劃分」問題，但卻不能解決「帶異質限制條件的集合劃分」問題。如要解決後一類問題，我們要採用新的方法，這將留待下節再討論。
接下來筆者要簡單討論「集合劃分問題的列舉型母函數」。在《點算的奧秘：列舉型母函數》中，筆者指出我們可以用
來列舉從n類物件(用A1 ... An代表)中可重覆地抽r個出來排序的問題的所有「排列」方案，惟須注意上式中的乘法為「非交換乘法」。根據《點算的奧秘：分配問題》的表2，「集合(無序)劃分」問題對應著「抽象排列」問題，因此我們可以借助「排列」問題與「抽象排列」問題之間的關係來找出「集合(無序)劃分」問題的「列舉型母函數」。「抽象排列」其實就是把某些「排列」視作等同，因此我們可以透過把符合某些限制條件的所有「排列」方案進行「同類項合併」的方法來找出相應的所有「抽象排列」方案，筆者用以下例題說明上述方法。
例題3：列出把4個元素劃歸3個(無序)非空子集的所有「劃分」方案。
答3：上述「集合(無序)劃分」問題對應著以下「抽象排列」問題：從3類沒有固定編號的物件中可重覆地抽4個出來排序，並且每類物件須至少抽1個出來。我們首先解決與此問題相關的「排列」問題。把n = 3，r = 4代入算式(7)，
把上式展開後，我們首先要進行一番「篩選」工作，捨棄那些不符合本題限制條件，即不同時包含A、B和C的項(例如AAAA、BCBC等)。經過「篩選」後，我們得到以下36個「排列」方案：
接著我們對以上36個項進行「同類項合併」。合併方法是把以上各項改寫為「規範形式」(Canonical Form)，用數字1、2、3分別代替各項中第一、第二、第三個出現的字母，相同的字母要用相同的數字代替。對於重覆出現的「規範形式」，只保留一個。上述改寫過程的實質是把各「排列」方案轉化為相應的「抽象排列」方案。舉例說，根據上述改寫規則，AABC、AACB、BBAC、BBCA、CCAB、CCBA都被改寫成1123，因為上述6個「排列」方案都對應著以下這個「抽象排列」方案：「把其中一類物件放在位置1和2，把其餘兩類物件分別放在位置2和3」。經「同類項合併」後，只剩下下列6個「抽象排列」方案：
接著我們利用「抽象排列」問題與「集合(無序)劃分」問題的對應關係，把以上6項轉化為對應的「(無序)劃分」方案：
上述6個「(無序)劃分」方案就是我們要求的答案。□
可以想見，當「集合(無序)劃分」問題的「參數」很大或者涉及複雜的限制條件時，以上解題方法會變得很繁瑣，因為我們要做大量「篩選」、「合併同類項」和轉化的工作。不過，筆者認為如果我們能設計適當的「算法」，讓電腦去做上述繁瑣的工作，以上解題方法也不失為解答「列舉型集合劃分」問題的有效方法。
最後，筆者要指出上述的「合併同類項」其實不是甚麼新奇的概念。我們知道，「組合」也可視為把某些「排列」視作等同，因此對於上題的36個「排列」方案，我們也可把它們改為成「規範形式」以找出相應的「組合」方案，改寫的方法是把各項的字母按字母表順序重新排序，例如把CABA改寫為AABC。經改寫和「合併同類項」後，該36個「排列」方案便變成以下3個「組合」方案：
由此可見，「集合(無序)劃分」方案和「組合」方案都可看成是對「排列」方案進行「合併同類項」後的結果，只不過兩者對「同類」的定義各有不同而已。這一點令我們對《點算的奧秘：分配問題》表2中四大「點算組合學」問題之間的關係有更深入的認識。
註1：根據《點算的奧秘：分配問題》，「集合有序劃分」問題對應著「排列」問題，因此「排列」問題的「母函數」也就是「集合有序劃分」問題的「母函數」。