在《點算的奧秘：集合劃分問題的母函數》中，筆者介紹了如何用「母函數」方法求解「帶同質限制條件的集合劃分」問題。但這種方法對於「帶異質限制條件的集合劃分」問題卻是無能為力。我們首先從一種特殊的「集合劃分」問題開始，此即「規定子集元素個數的集合(無序)劃分」問題。試看以下例題。
例題1：現要把5個元素劃歸3個(無序)子集，並規定其中兩個子集各有1個元素，第三個子集含有3個元素，問有多少種不同的劃分法？
答1：為使我們的解答具有概括性，我們仍然嘗試把本題表達為某種「母函數」。我們首先考慮與本題相關的「規定子集元素個數的集合有序劃分」問題。為方便以下討論，我們把本題答案記為P(1, 1, 3)，並把相關的「有序劃分」問題的答案記為D(1, 1, 3)。鑑於筆者在前一節曾指出「異質限制條件」會令我們的「母函數」方法失效，而本題的限制條件又正是「異質」的，我們不能直接把求D(1, 1, 3)的問題表達為「母函數」。因此我們改為考慮一個一般的「集合有序劃分」問題，即把5個元素劃歸3個非空有序子集A1、A2和A3的問題，亦即前一節所述的求D1(5, 3)的問題。根據前一節，D1(5, 3)的「指數母函數」為
請注意在上式中，每個「括弧」代表一個子集，「括弧」中的xr/r!則代表該子集內有r個元素。而且各個「括弧」的內容完全相同，這樣各個子集是對稱的，從而避免了「異質限制條件」所帶來的問題。可是我們的目的不是求D1(5, 3)，而是求D(1, 1, 3)。不過為了弄清楚D(1, 1, 3)與D1(5, 3)的關係，我們須先了解D1(5, 3)是如何求得的。D1(5, 3)就是上式展開式中x5 / 5!項的「系數」。為求得這個「系數」，我們要從上面3個「括弧」中各抽取一項，使得它們相乘後會得到x5項。這些項包括：
| (1) x, x, x3/3! (2) x, x2/2!, x2/2! (3) x, x3/3!, x (4) x2/2!, x, x2/2! (5) x2/2!, x2/2!, x (6) x3/3!, x, x |
以上各行其實代表把5個元素劃歸3個有序子集的各種可能模式，例如第(1)行便代表把1個元素放入A1，把1個元素放入A2，並把3個元素放入A3。在上述6行中，(1)、(3)和(6)便是符合本題限制條件的「有序劃分」模式。由此可見，在計算D1(5, 3)的過程中，我們其實已掌握了求D(1, 1, 3)的資料，但是我們的計算過程沒有把這些資料跟其他無助於求D(1, 1, 3)的資料(即上面的(2)、(4)和(5))區分開來。因此現在我們需要設法識別這些資料，方法是把代表整數1、2 ...的N1、N2 ...加入上面的算式(1)：
有了N1、N2 ...這些記號，我們便可以把D(1, 1, 3)定為上式展開式中N12N3x5 / 5!項的「系數」。請注意這裡的N12N3代表本題的限制條件，x5/5!則代表共有5個元素。接著讓我們求這個「系數」。從上面3個「括弧」中各抽取對應於上面第(1)、(3)和(6)行中的項，把它們相乘然後相加，便得到
| N12N3x5/3! + N12N3x5/3! + N12N3x5/3! | |
| = | 60N12N3x5/5! |
由此得到D(1, 1, 3) = 60。這個數就是把5個元素劃歸3個有序子集，並符合本題規定的限制條件的「劃分」方案總數。現在如何從D(1, 1, 3)推導出我們所求的答案P(1, 1, 3)？由於給定3個(無序)子集，我們可以構造出3! = 6個相應的有序子集，因此D(1, 1, 3) = 6 × P(1, 1, 3)，即P(1, 1, 3) = 60 / 6 = 10。□
我們可以把以上結果推廣至一般的「規定子集元素個數的集合(無序)劃分」問題：
| 現要把r個元素劃歸n個(無序)非空子集，並且規定這些子集須滿足以下條件： (a) k1個子集有1個元素 ... kr個子集有r個元素； (b) k1 ≥ 0 ... kr ≥ 0； (c) k1 + ... rkr = r； (d) k1 + ... kr = n 問共有多少種劃分法？ |
我們把以上問題的答案記為P(k1, ... kr)。
為了求解上題，我們考慮一個相關的「規定子集元素個數的集合有序劃分」問題，並把其答案記為D(k1, ... kr)。顯然上述兩個問題的答案滿足以下關係式：
為了避免「異質限制條件」帶來的問題，我們改為考慮一個一般的「集合有序劃分」問題，即把r個元素劃歸n個非空有序子集的問題，亦即求D1(r, n)的問題，這個問題的「指數母函數」為
接著我們把代表整數1、2 ...的N1、N2 ...加入上面的算式：
D(k1, ... kr)就是上式展開式中N1k1 ... Nrkr xr / r!項的「系數」。由此應有以下等式：
請注意在上式中，r、k1 ... kr都是會變化的參數(儘管它們必須滿足上面的條件c)，因此上式包含兩層求和符號Σ以代表對這些參數求和，其中外層的Σ代表對r求和(這裡r的下限為n是因為本題中的n個子集都是非空子集，因此元素的數目r至少須等於n)，內層的Σ則代表對其他參數求和，其下標(b)-(d)是表示對滿足上述條件(b)-(d)的所有k1 ... kr求和。
把上式等號左、右兩端同時除以n!，並利用公式(2)，便得到
| (N1x + N2x2/2! + N3x3/3! ...)n / n! | = [Σn ≤ r < ∞ Σ(b)-(d) D(k1, ... kr) N1k1 ... Nrkr xr/r!] / n! |
| = Σn ≤ r < ∞ Σ(b)-(d) [D(k1, ... kr) / n!] N1k1 ... Nrkr xr/r! (註1) | |
| = Σn ≤ r < ∞ Σ(b)-(d) P(k1, ... kr) N1k1 ... Nrkr xr/r! |
上式中的Σ(b)-(d) P(k1, ... kr) N1k1 ... Nrkr在「點算組合學」上稱為「部分貝爾劃分多項式」(Partial Bell Partition Polynomial)，一般記作Br,n。利用這個符號，上式可簡化為
經過以上計算，我們得到「求Br,n的指數母函數」：
Br,n就是上式展開式中xr / r!項的「系數」。不過我們的主要目的不是求Br,n，而是求P(k1, ... kr)，因此我們不妨把公式(3)看成「求P(k1, ... kr)的多元母函數」(註3)，這個「多元母函數」(Multivariate Generating Function)包含r、k1, ... kr等多個參數，P(k1, ... kr)就是上式展開式中N1k1 ... Nrkr xr / r!項的「系數」。
接著讓我們展開公式(3)以尋求上述「系數」。公式(3)由n個「括弧」組成。如要相乘得到上述這個項，我們必須從這n個「括弧」中抽出k1個N1x ... kr個Nrxr/r!。把上述這些項相乘後，便得到
| N1k1 / (1!)k1 × ... Nrkr / (r!)kr × xk1 + ... rkr | |
| = | N1k1 ... Nrkr xr / [(1!)k1 × ... (r!)kr] (4) |
可是，從這n個「括弧」中抽出k1個N1x ... kr個Nrxr/r!出來，不只有一種方法。事實上，給定一種抽法，只要調換一下各個「括弧」的次序，便可能得到另一種抽法(因為所有「括弧」的內容完全相同)。那麼究竟有多少種抽法？只要細心想想，不難發現這個問題的答案其實就是以下「有限重覆全排列」問題的答案：
| 有r類物件，第1類物件有k1個 ... 第r類物件有kr個， 並且k1 + ... kr = n， 現要把這n個物件排序，問有多少種不同排法？ |
根據「有限重覆全排列」公式，上述問題共有n! / [(k1)! × ... (kr)!]種排法。換句話說，共有n! / [(k1)! × ... (kr)!]種抽法可令我們得到上面算式(4)。現在把這個數與算式(4)相乘，並乘以1 / n! (不要忘記公式(3)含有1 / n!這個因子)和r! / r! (這是要使最後計算出來的項有r!作為分母)，便可得到
| n! | N1k1 ... Nrkr xr | 1 | r! | |||||
| ----------------------- | × | ----------------------------- | × | ------ | × | ------ | ||
| (k1)! × ... (kr)! | (1!)k1 × ... (r!)kr | n! | r! | |||||
| r! | N1k1 ... Nrkr xr | |||||||
| = | ----------------------------------- | × | ------------------------- | |||||
| (k1)! (1!)k1 × ... (kr)! (r!)kr | r! |
我們最終求得P(k1, ... kr)為
上述結果跟《點算的奧秘：集合劃分問題》中的公式(9)完全相同。至此我們有兩個方法計算P(k1, ... kr)，我們可以借助「求Br,n的母函數」(即公式(3))間接求這個數，也可用公式(5)直接求這個數。
接下來我們便可以綜合運用本節以及前面數節所曾介紹的方法來解決「帶異質限制條件的集合劃分」問題。以下用一個例題來說明解題方法。
例題2：現要把6個元素劃歸2個(無序)非空子集，並規定其中一個子集至少包含3個元素，另一個子集最多包含4個元素，問有多少種不同的「(無序)劃分」方案？
答2：本題就是《點算的奧秘：集合劃分問題的母函數》中的問題A。在該網頁中，筆者曾指出本題的「異質限制條件」令我們的「母函數」方法失效，現在我們嘗試循另一思路解答本題。
我們可以把解答本題的程序分成兩步。在第一步，我們暫不理會把哪些元素放入哪個子集的問題，而只考慮每個子集應包含多少個元素的問題。這實際上等同於求解以下這個「整數分割」問題：現要把6分割為2個部分，其中一部分不小於3，另一部分不大於4。試列出所有「分割」方案。
請注意上述「整數分割」問題跟筆者在前面數節介紹過的「整數分割」問題很不相同。不過由於現在我們的目的是「列舉」所有符合條件的「分割」方案而非「計算」這些方案的數目，我們可不妨用以下這個「列舉型母函數」來求解：
容易看到上式展開式中x6項的「系數」為
上述3個「分割」方案：3+3、2+4和1+5其實代表每個子集所應包含元素個數的3種不同方案。有了上述3個方案，我們便可以進行解題程序的第二步，應用前面求解「規定子集元素個數的集合(無序)劃分」問題的方法來找出符合本題限制條件的所有「(無序)劃分」方案。把n = 2代入公式(3)
根據前面的討論，本題答案就是上式展開式中N32x6 / 6!、N2N4x6 / 6!和N1N5x6 / 6!項的「系數」之和。這個「系數」的計算過程如下：
| N32x6 / 6!項： | [N32x6/(3!3!)] / 2! | |
| = | 10N32x6/6! | |
| N2N4x6 / 6!項： | [N2N4x6/(2!4!) + N2N4x6/(4!2!)] / 2! | |
| = | 15N2N4x6/6! | |
| N1N5x6 / 6!項： | [N1N5x6/5! + N1N5x6/5!] / 2! | |
| = | 6N1N5x6/6! |
因此本題答案為10 + 15 + 6 = 31。□
上題的解題程序與以往筆者介紹的「有限重覆部分排列」問題的解題程序非常相似(請參閱《點算的奧秘：帶上、下限的排列組合問題》)，兩者都分為兩步進行，在第一步中我們首先找出所有符合給定限制條件的「整數(無序)分割」／「組合」方案，在第二步中我們應用求解「規定子集元素個數的集合(無序)劃分」問題／「有限重覆全排列」問題的公式或「母函數」來找出我們要求的答案。由此可見，「集合(無序)劃分」與「整數(無序)分割」問題之間的關係類似「排列」與「組合」問題之間的關係，這再一次證實了《點算的奧秘：分配問題》中表2的合理性。