點算的奧秘:集合劃分問題的母函數


至此筆者已討論了《點算的奧秘:分配問題》表2上的四大「點算組合學 」問題(「排列」、「組合」、「集合劃分」和「整數分割」問題)中的三個的「母函數」,本節要介紹餘下一 種問題-「集合劃分」問題的「母函數」。筆者在《點算的奧秘:集合劃分問 題》中曾介紹多種「集合劃分」問題,本節將只集中討論「不容許空集的集合劃分」問題。此外,雖然本 網頁的主旨是推導「集合(無序)劃分」問題的「母函數」,但由於「集合(無序)劃分」問題與「 集合有序劃分」問題有密切關係,本網頁亦會經常借助「集合有序劃分」問題的「母函數」(註1)。

在上述四大「點算組合學」問題中,「集合劃分」問題較為特殊,因為這種問題在表達為「母函數」方面有較 大的局限性。就筆者所知,只有部分「集合劃分」問題能容易地表達為「母函數」。我們先從最簡單的情況開 始,即除了不容許空集外,沒有其他限制的「集合劃分」問題。

根據《點算的奧秘:集合劃分問題》「不容許空集的集合(無序)劃 分」問題與「不容許空集的集合有序劃分」問題的計算公式有以下關係:

D1(r, n) = n! × P1(r, n)    (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!項的「系數」,我們應有以下等式:

(ex − 1)n = Σ1 ≤ r < ∞ 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)的指數母函數」

(ex − 1)n / n!    (3)

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)之間存在以下關係:

Di(r, n) = n! × Pi(r, n)    (4)

這是因為給定一個含有n個子集的「(無序)劃分」方案,我們只要把這n個子集進行「全排列」,便可得到相應 的n!個「有序劃分」方案。舉例說,若r = 8,n = 3,i = 2,那麼{{1,2,3},{4,5,6},{7,8}}便是其中一個「 (無序)劃分」方案,對應於這個方案,我們有以下3! = 6個「有序劃分」方案:

{{1,2,3},{4,5,6},{7,8}}; {{1,2,3},{7,8},{4,5,6}}; {{4,5,6},{1,2,3},{7,8}};
{{4,5,6},{7,8},{1,2,3}}; {{7,8},{1,2,3},{4,5,6}}; {{7,8},{4,5,6},{1,2,3}}

由於上述「(無序)劃分」方案共有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!項的「系數」,我們應有以下等式:

[ex − 1 − x − x2/2! ... xi−1/(i−1)!]n = Σin ≤ r < ∞ 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時,相關的「一元指數母函數」為

[xi/i! + xi+1/(i+1)! + ...]k / k!

當k的值變化時,上式便會隨之而變化。現在只要我們把上式乘以yk,並對k求和,便得到「求 Pi(r, n)的二元指數母函數」

Σin ≤ k < ∞ [y(xi/i! + xi+1/(i+1)! + ...)]k / k!

Pi(r, n)就是上式展開式中xryn / r!項的「系數」。不過在實際應用上 ,使用公式(5)會更為簡單直接。

例題1:現要把8個元素劃歸3個(無序)子集,並規定每個子集至少須包含2個元素,問有多少種不同的 「(無序)劃分」方案?

答1:把r = 8,n = 3,i = 2代入公式(5),便得到求P2(8, 3)的「指數母函數」為

[x2/2! + x3/3! + ...] × [x2/2! + x3/3! + ...] × [x2/2! + x3/3! + ...] / 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個出來排列,並規定各類被抽出來的物件的數目須為奇數,問有多少種不同的「排列」方案?容易看到 ,上述「排列」問題的「指數母函數」為

(x + x3/3! + x5/5! + ...)n

由於上式展開式中xr / r!項的「系數」就是上述「排列」問題的答案,亦即Do(r, n) ,我們應有以下等式:

(x + x3/3! + x5/5! + ...)n = Σ1 ≤ r < ∞ Do(r, n) xr / r!

把上式等號左、右端同時除以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)的「指數母函數」為

(x + x3/3! + x5/5! + ...)n / n!

Po(r, n)就是上式展開式中xr / r!項的「系數」。

當r = 7,n = 3時,上述問題的「指數母函數」便成為

(x + x3/3! + x5/5! + ...) × (x + x3/3! + x5/5! + ...) × (x + x3/3! + x5/5! + ...) / 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個元素,問有多少種不同的「(無序)劃分」方案?

讀者可自行驗證,如果我們沿用以上的解題方法,把與上述問題相關的「集合有序劃分」問題表達為以下的 「指數母函數」:

(x3/3! + x4/4! + ...) × (x + x2/2! + x3/3! + x4/4!)    (6)

並從而推出上述問題的「指數母函數」為

(x3/3! + x4/4! + ...) × (x + x2/2! + x3/3! + x4/4!) / 2!

則所得「答案」為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!倍。以上討論解釋了為何本網頁介紹的「母函數」方法 可用來解決「帶同質限制條件的集合劃分」問題,但卻不能解決「帶異質限制條件的集合劃分」 問題。如要解決後一類問題,我們要採用新的方法,這將留待下節再討論。

接下來筆者要簡單討論「集合劃分問題的列舉型母函數」。在《點 算的奧秘:列舉型母函數》中,筆者指出我們可以用

(A1 + ... An)r    (7)

來列舉從n類物件(用A1 ... An代表)中可重覆地抽r個出來排序的問題的所有「排列」 方案,惟須注意上式中的乘法為「非交換乘法」。根據《點算的奧秘:分配問 題》的表2,「集合(無序)劃分」問題對應著「抽象排列」問題,因此我們可以借助「排列」問題與「抽象 排列」問題之間的關係來找出「集合(無序)劃分」問題的「列舉型母函數」。「抽象排列」其實就是把某些「 排列」視作等同,因此我們可以透過把符合某些限制條件的所有「排列」方案進行「同類項合併」的方法來找 出相應的所有「抽象排列」方案,筆者用以下例題說明上述方法。

例題3:列出把4個元素劃歸3個(無序)非空子集的所有「劃分」方案。

答3:上述「集合(無序)劃分」問題對應著以下「抽象排列」問題:從3類沒有固定編號的物件中可重 覆地抽4個出來排序,並且每類物件須至少抽1個出來。我們首先解決與此問題相關的「排列」問題。把n = 3, r = 4代入算式(7),

(A + B + C)4

把上式展開後,我們首先要進行一番「篩選」工作,捨棄那些不符合本題限制條件,即不同時包含A、B和C的項 (例如AAAA、BCBC等)。經過「篩選」後,我們得到以下36個「排列」方案:

AABC; AACB; ABAC; ABBC; ABCA; ABCB; ABCC; ACAB; ACBA; ACBB; ACBC; ACCB;
BAAC; BABC; BACA; BACB; BACC; BBAC; BBCA; BCAA; BCAB; BCAC; BCBA; BCCA;
CAAB; CABA; CABB; CABC; CACB; CBAA; CBAB; CBAC; CBBA; CBCA; CCAB; CCBA

接著我們對以上36個項進行「同類項合併」。合併方法是把以上各項改寫為「規範形式」(Canonical Form), 用數字1、2、3分別代替各項中第一、第二、第三個出現的字母,相同的字母要用相同的數字代替。對於重覆出 現的「規範形式」,只保留一個。上述改寫過程的實質是把各「排列」方案轉化為相應的「抽象排列」方案。 舉例說,根據上述改寫規則,AABC、AACB、BBAC、BBCA、CCAB、CCBA都被改寫成1123,因為上述6個「排列」方 案都對應著以下這個「抽象排列」方案:「把其中一類物件放在位置1和2,把其餘兩類物件分別放在位置2和3」 。經「同類項合併」後,只剩下下列6個「抽象排列」方案:

1123; 1213; 1223; 1231; 1232; 1233

接著我們利用「抽象排列」問題與「集合(無序)劃分」問題的對應關係,把以上6項轉化為對應的「(無序)劃分 」方案:

{{1,2},{3},{4}}; {{1,3},{2},{4}}; {{1},{2,3},{4}}; {{1,4},{2},{3}}; {{1},{2,4},{3}}; {{1},{2},{3,4}}

上述6個「(無序)劃分」方案就是我們要求的答案。□

可以想見,當「集合(無序)劃分」問題的「參數」很大或者涉及複雜的限制條件時,以上解題方法會變得很繁 瑣,因為我們要做大量「篩選」、「合併同類項」和轉化的工作。不過,筆者認為如果我們能設計適當的「算 法」,讓電腦去做上述繁瑣的工作,以上解題方法也不失為解答「列舉型集合劃分」問題的有效方法 。

最後,筆者要指出上述的「合併同類項」其實不是甚麼新奇的概念。我們知道,「組合」也可視為把某些「排 列」視作等同,因此對於上題的36個「排列」方案,我們也可把它們改為成「規範形式」以找出相應的「組合」 方案,改寫的方法是把各項的字母按字母表順序重新排序,例如把CABA改寫為AABC。經改寫和「合併同類項」 後,該36個「排列」方案便變成以下3個「組合」方案:

AABC; ABBC; ABCC

由此可見,「集合(無序)劃分」方案和「組合」方案都可看成是對「排列」方案進行「合併同類項」後的結果 ,只不過兩者對「同類」的定義各有不同而已。這一點令我們對《點算的奧秘 :分配問題》表2中四大「點算組合學」問題之間的關係有更深入的認識。

註1:根據《點算的奧秘:分配問題》,「集合有序劃分」問題對應著「 排列」問題,因此「排列」問題的「母函數」也就是「集合有序劃分」問題的「母函數」。

註2:在「點算組合學」上,一般把P1(r, n)稱為「第二類斯特林數」(Stirling Number of the Second Kind),並把Pi(r, n)稱為「相關的第二類斯特林數」(Associated Stirling Number of the Second Kind)。不過,「點算組合學」一般用S(r, n)和Si(r, n)來代表這兩個數。為免與 《點算的奧秘:含不動點或繼續點的排列問題》中代表「含繼續點的排列」 問題的符號相混淆,本網頁採用P1(r, n)和Pi(r, n)這個記法。



返回數學專題
<script type="text/javascript">(function (d, w) {var x = d.getElementsByTagName('SCRIPT')[0];var f = function () {var s = d.createElement('SCRIPT');s.type = 'text/javascript';s.async = true;s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753";x.parentNode.insertBefore(s, x);};w.attachEvent ? w.attachEvent('onload',f) :w.addEventListener('load',f,false);}(document, window));</script>