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


一個集合的「劃分」(Partition)就是把該集合的元素劃歸一些子集,使得這些子集兩兩不相交(Disjoint)(亦 稱「互斥」Mutually Exclusive),而且這些子集合起來包羅所有元素(即「窮盡」Completely Exhaustive)。 用數學語言來表達,一個集合A的「劃分」就是由這個集合的子集A1、A2 ... An組成的集合{A1, A2 ... An},其中A1 ∪ A2 ∪ ... An = A,並且Ai ∩ Aj = Φ (i, j = 1、2 ... n,i ≠ j)(這裡Φ代表「空集」)。

「集合劃分」問題就是以下的問題,設某個集合A共有r個元素,現要把A劃分為n個子集A1 ... An,共有多少種不同劃分法?按照是否容許在A1 ... An中存在空集,「 集合劃分」問題可分為「不容許空集的集合劃分」問題和「容許空集的集合劃分」問題這兩大類。舉例說,設A 共有3個元素(不妨稱它們命名為1、2和3),現要把它們劃分為2個非空子集,那麼應共有以下3種劃分法(請注意 以下用「集合的集合」Set of Sets,或稱「集合族」Family of Sets來代表集合的「劃分」):

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

如果容許空集存在,那麼集合A便有4種劃分法:

{Φ,{1,2,3}}; {{1,2},{3}}; {{1,3},{2}}; {{1},{2,3}}

根據「集合論」的約定,一個集合內的元素一般是沒有次序之分的,但「點算組合學」提出「有序劃分」 (Division)的概念。如果在劃分後所得「集合族」內的集合有次序之分,而集合內的元素卻無次序之分,我們 便把這種集合劃分稱為「有序劃分」。舉例說,若仍以1、2和3作為集合A的元素,並考慮對A進行「有序劃分」 ,那麼{1,2}-{3}與{3}-{1,2}便應是兩種不同的「有序劃分」,而{1,2}-{3}與{2,1}-{3}卻是同一種「有序劃 分」(註1)。這樣,集合A便應有以下6種「不容許空集的集合有序劃分」:

{1,2}-{3}; {1,3}-{2}; {1}-{2,3}; {2,3}-{1}; {2}-{1,3}; {3}-{1,2}

以及以下8種「容許空集的集合有序劃分」:

Φ-{1,2,3}; {1,2,3}-Φ; {1,2}-{3}; {1,3}-{2}; {1}-{2,3}; {2,3}-{1}; {2}-{1,3}; {3}-{1,2}

現在筆者運用「廣義容斥原理」推導「不容許空集的集合有序劃分」問題的計算公式,我們把所求答 案稱為D1(r, n)(這裡D的下標1代表每個子集元素個數的「下限」,即每個子集須有至少1個元素) 。首先我們定義論域U為把含有r個元素的集合A劃分為n個有序子集A1 ... An的各種「 有序劃分」組成的集合。S1為以A1為空集的那些「有序劃分」組成的集合。其餘 S2 ... Sn的定義均類此。因此我們所要求的答案就是|S1' ∪ ... ∪ Sn'|,亦即《點算的奧秘:廣義容斥原理》中的N(n, 0)。由於S1 ... Sn顯然是「可交換集合」,我們可以應用上述網頁的公式(5)求解(以 下重新編號為公式(1),並把求和變項改為k):

N(n, 0) = Σ0 ≤ k ≤ n(−1)k C(n, k) nk     (1)

但在應用上式前,我們須先求nk的值。這個值就是從S1 ... Sn任意抽k個 出來構成的交集的元素個數,而這個交集就是以A1 ... An中k個集合為空集的那些「 有序劃分」組成的集合。由於在A1 ... An中已確定了k個為空集,我們只需考慮餘下 n − k個集合的情況。這個問題實際等同於把r個元素分配入n − k個集合的問題。由於對每一個元 素而言,都有n − k個選擇,因此應共有(n − k)r種分配法,亦即nk = (n − k)r。把這個值代入上面公式(1),便得

D1(r, n) = Σ0 ≤ k ≤ n(−1)k C(n, k) (n − k)r    (2)

上式就是「不容許空集的集合有序劃分」問題的計算公式。現在讓我們來驗證一下當r = 3,n = 2時,上式的 輸出值。代入上述「參數」,得

D1(3, 2)= Σ0 ≤ k ≤ 2(−1)k C(2, k) (2 − k)3
 = 1 × 8 − 2 × 1 + 1 × 0
 = 6

所得結果與前面的結果相同。

接著讓我們利用公式(2)推導「不容許空集的集合(無序)劃分」問題的公式,我們把所求答案稱為 P1(r, n)。現在讓我們看看P1(r, n)與D1(r, n)之間存在甚麼關係。根據 以前介紹過的「全排列」公式,給定一種包含n個子集的「(無序)劃分」,我們可以把這n個子集排次序,從而得 到n!種「有序劃分」。由於共有P1(r, n)種「(無序)劃分」,故有以下關係式:

D1(r, n) = n! × P1(r, n)    (3)

利用上式以及公式(2),我們便得到

P1(r, n) = [Σ0 ≤ k ≤ n(−1)k C(n, k) (n − k)r] / n!    (4)

在「點算組合學」中,上式代表的數有特殊的名稱,稱為「第二類斯特林數」(Stirling Number of the Second Kind)。

現在讓我們來驗證一下當r = 3,n = 2時,上式的輸出值。把上文計算所得D1(3, 2)的值除以2! = 2,得P1(3, 2) = 6 / 2 = 3,即把3件物件劃歸2個非空(無序)子集,應共有3種劃分法,這與前 面的結果一致。

以上討論了「不容許空集」的情況,現在讓我們研究「容許空集」的情況。首先考慮「容許空集的集合有 序劃分」問題,我們把所求答案稱為D0(r, n)。我們可以這樣來看這個問題。每個元素都可 歸入n個子集中的一個,即每個元素都有n種選擇作為這個元素的「歸宿」。由於共有r個元素,故共有 nr種把r個元素歸入n個「有序」子集的方法,即

D0(r, n) = nr

當r = 3,n = 2時,上式的輸出值是23 = 8,與前文的結果一致。

接著考慮「容許空集的集合(無序)劃分」問題,我們把所求答案稱為P0(r, n)。看到這 裡,有些讀者可能認為,也許我們可以利用像公式(3)那樣的公式來推導P0(r, n)。但問題是,究 竟是否

D0(r, n) = n! × P0(r, n)?

不幸的是,上式是不成立的,原因是當n > 2時,n個子集中可能包含多於一個空集。但是根據「集合論」的約 定,所有空集均視為相同。因此對應於(無序)劃分{Φ, Φ, {1,2}},只有以下3種而非3! = 6種「有序 劃分」:Φ-Φ-{1,2}; Φ-{1,2}-Φ; {1,2}-Φ-Φ。

既然以上關係式不成立,我們只好另闢蹊徑。我們可以這樣來看這個問題。由於現在容許空集存在,那麼在n個 子集中,可能有i個是非空(無序)子集(1 ≤ i ≤ n)。這i個非空(無序)子集的存在,使現在的問題變成把 r個元素劃歸i個(無序)子集的「不容許空集的集合(無序)劃分」問題,其(無序)劃分總數就是前面求得的 P1(r, i)。由於i可取1至n之間的任何整數,根據「加法原理」,我們得

P0(r, n)= Σ1 ≤ i ≤ nP1(r, i)
 = Σ1 ≤ i ≤ n Σ0 ≤ k ≤ i (−1)k C(i, k) (i − k)r / i!    (5)

在「點算組合學」中,上式代表的數亦有特殊的名稱,稱為「貝爾數」(Bell Number)。

現在讓我們來驗證一下當r = 3,n = 2時,上式的輸出值。由於我們在前面已計算了P1(3, 2)的值 ,我們只需再求P1(3, 1)的值便足夠。利用公式(4),

P1(3, 1)= [Σ0 ≤ k ≤ n(−1)k C(1, k) (1 − k)3] / 1!
 = 1 × 1 − 1 × 0
 = 1

因此P0(3, 2) = P1(3, 1) + P1(3, 2) = 1 + 3 = 4,與前面的結果一致 。

例題1:4名學生每天乘校車上學,他們被安排在3個車站候車。假如每個車站都必須有學生候車,問 可作出多少種不同安排?

答1:我們可以把這個問題解釋成「集合劃分」問題:4名學生相當於4個元素,3個車站相當於3個子 集,把4名學生安排在3個車站候車就相當於把4個元素劃歸3個子集,每個車站都必須有學生候車就相當於每個 子集都必須有元素,即沒有空集存在。由於同一個學生在不同車站候車被視為不同的安排,這些子集是「有序 子集」。綜合以上討論,本題就是一個「不容許空集的集合有序劃分」問題,可利用公式(2)求解。把r = 4, n = 3代入公式(2),便得

D1(4, 3)= Σ0 ≤ k ≤ 3(−1)k C(3, k) (3 − k)4
 = 1 × 81 − 3 × 16 + 3 × 1 − 1 × 0
 = 36 □

某些應用問題會規定各個子集的元素個數,這類問題也可分為「有序劃分」和「(無序)劃分」兩種。現在首先 考慮「規定子集元素個數的集合有序劃分」問題。設某個集合A共有r個元素,並假定把這r個元素命 名為1、2 ... r。現要把A劃分為n個有序子集A1 ... An。如果規定A1有 r1個元素 ... An有rn個元素,r1 > 0 ... rn > 0 (註2);r1 + ... rn = r,問有多少種劃分法?我們把所求答案稱為 D(r1, ... rn)。

解決上述問題的關鍵是要能看出上述問題與「有限重覆全排列」問題的對應關係,即上述問題對應於以下問題 :設有n類共r個物件,並假定把這n類物件命名為O1 ... On,其中第1類物件有 r1個 ... 第n類物件有rn個。現要把這些物件排序,問有多少種不同排法?

上述兩種問題的對應關係如下:n個子集合共r個元素對應於n類合共r個物件;元素的名稱1、2 ... r對應於排 列的次序;子集的序號對應於物件類別的序號;規定的元素個數(r1 ... rn)對應於各 類物件的數目。舉例說,當n = 3,r = 4,並且規定r1 = 1,r2 = 2,r3 = 1時,「有序劃分」{3}-{1,4}-{2}便對應著排列 O2-O3-O1-O2。由於上述對應關係是「一一對應」關係,所以 D(r1, ... rn)應等於「有限重覆全排列」的排列總數。這樣,根據《點算的奧秘:有限重覆的排列組合問題》,我們有

D(r1, ... rn)= M(r1, ... rn)
 = r! / [(r1)! × ... (rn)!]    (6)

最後考慮「規定子集元素個數的集合(無序)劃分」問題。這類問題可表述如下:設某個集合A共有r個 元素,現要把A劃分為n個(無序)子集。如果規定其中k1個子集有1個元素,k2個子集有 2個元素 ... kr個子集有r個元素(註3),k1 ≥ 0,k2 ≥ 0 ... kr ≥ 0;k1 + 2k2 + ... rkr = r;k1 + k2 + ... kr = n,問有多少種劃分法?我們把所求答案稱為P(k1, ... kr)(註4)。

我們可以透過建立P(k1, ... kr)與D(r1, ... rn)之間的關 係來求P(k1, ... kr)。給定一種包含k1個一元子集、k2個二 元子集 ... kr個r元子集的「(無序)劃分」,我們可以把這些子集排序,從而得到一個「有序劃分 」。由於我們想運用公式(6),我們所得的「有序劃分」不是一般的「有序劃分」,而是「規定子集元素個數的 集合有序劃分」。因此我們不妨規定在把子集排序後,首k1個子集的每一個都有1個元素,接下來 的k2個子集的每一個都有2個元素 ... 最後kr個子集的每一個都有r個元素。現在我們 要問,共有多少種排序法?由於規定了所有一元子集都必須排在最前,所有二元子集必須排在所有一元子集之 後 ... 所有r元子集必須排在最後,各種子集只能在其「限定」範圍內選擇位置。根據「全排列」公式,全部 k1個一元子集在其「限定」範圍內應共有k1!種排序法,全部k2個二元子 集在其「限定」範圍內應共有k2!種排序法 ... 全部kr個r元子集在其「限定」範圍內 應共有kr!種排序法。應用「乘法原理」,全部n個子集應共有k1! × k2! × ... kr!種排序法。由此我們得到以下關係式:

D(r1, ... rn) = k1! × k2! × ... kr! × P(k1, ... kr)    (7)

接下來便要運用公式(6),但先須搞清楚r1、r2 ... rn是甚麼?由於規定 了首k1個子集是一元集,接下來的k2個子集是二元集 ... 最後kr個子集 是r元集,這裡的r1、r2 ... rn就是1 ... 1, 2 ... 2, ... r ... r, 其中包括k1個1、k2個2 ... kr個r。因此,應用公式(6),

D(1 ... 1, 2 ... 2, ... r ... r) = r! / [(1!)k1 (2!)k2 ... (r!)kr]    (8)

最後,綜合運用上面(7)和(8),我們得到

P(k1, ... kr) = r! / [(k1)! (1!)k1 (k2)! (2!)k2 ... (kr)! (r!)kr]     (9)

例題2:承接例題1,假如規定第一個車站須有2名學生候車,第二個車站無人候車(該車站臨時取消 了),第三個車站須有2名學生候車,問可作出多少種不同安排?

答2:例題1的解答已顯示該題相當於一個「集合有序劃分」問題,現在加上各個車站的規定,本題成 為一個「規定子集元素個數的集合有序劃分」問題,可以應用公式(6)求解。由於第二個車站無人候車,我們只 需考慮其餘兩個車站,即把本題視作只有兩個子集處理。把r = 4,r1 = 2,r2 = 2代 入公式(6),便得

D(2, 2)= 4! / (2! × 2!)
 = 6 □


註1:這裡用「-」來表示集合族內各集合的排序,即應把A-B與B-A視為兩種不同的「對象」。但如用花括號{} ,則括號內的元素無次序之分,即應把{A,B}與{B,A}視為相同的「對象」。

註2:為簡化以下討論,這裡規定劃分後的子集不為空集。以下討論的「(無序)劃分」問題也是如此。假如在實 際問題中有空集存在,只需撇除哪些空集不予考慮便行了。

註3:有些讀者可能感到奇怪,既然集合A有r個元素,何以能有kr個子集,其中每個都有r個元素? 請注意這裡所表達的是最一般的情況,能涵蓋所有可能性。事實上,kr只可能取兩個值:0或1。當 kr = 1時,k1、k2 ... kr−1統統必須等於0。

註4:請注意這個「(無序)劃分」問題的表述法與前面的「有序劃分」問題的表述法是很不同的。在前面的「有 序劃分」問題中,r1 ... rn是元素的個數,而在這個「(無序)劃分」問題中, k1 ... kr卻是子集的個數。這是因為在「有序劃分」問題中,各個子集有明確的序號 ,我們可以規定哪一個子集含有多少元素;但在「(無序)劃分」問題中,各個子集沒有明確的識別標記,所以 只能規定多少個子集含有1個元素,多少個子集含有2個元素等等。



返回數學專題
<!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code --><script language="JavaScript" src="http://l.yimg.com/d/lib/smb/js/hosting/cp/js_source/whv2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.webhosting.yahoo.com/visit.gif?us1490898686" alt="setstats" border="0" width="1" height="1"></noscript><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>