點算的奧秘:帶複雜條件的集合劃分問題


《點算的奧秘:集合劃分問題的母函數》中,筆者介紹了如何用「母函 數」方法求解「帶同質限制條件的集合劃分」問題。但這種方法對於「帶異質限制條件的集合劃 分」問題卻是無能為力。我們首先從一種特殊的「集合劃分」問題開始,此即「規定子集元素個數的集合 (無序)劃分」問題。試看以下例題。

例題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)的「指數母函數」為

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

請注意在上式中,每個「括弧」代表一個子集,「括弧」中的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):

(N1x + N2x2/2! + N3x3/3! + ...) × (N1x + N2x2/2! + N3x3/3! + ...) × (N1x + N2x2/2! + N3x3/3! + ...)

有了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)。顯然上述兩個問題的答案滿足以下關係式:

D(k1, ... kr) = n! × P(k1, ... kr)    (2)

為了避免「異質限制條件」帶來的問題,我們改為考慮一個一般的「集合有序劃分」問題,即把r個元素劃歸n 個非空有序子集的問題,亦即求D1(r, n)的問題,這個問題的「指數母函數」為

(x + x2/2! + x3/3! ...)n

接著我們把代表整數1、2 ...的N1、N2 ...加入上面的算式:

(N1x + N2x2/2! + N3x3/3! ...)n

D(k1, ... kr)就是上式展開式中 N1k1 ... Nrkr xr / r!項的「系數」。由此應有以下等式:

(N1x + N2x2/2! + N3x3/3! ...)n = Σn ≤ r < ∞ Σ(b)-(d) 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。 利用這個符號,上式可簡化為

(N1x + N2x2/2! + N3x3/3! ...)n / n! = Σn ≤ r < ∞ Br,n xr/r!

經過以上計算,我們得到「求Br,n的指數母函數」

(N1x + N2x2/2! + N3x3/3! ...)n / n!    (註2)(3)

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)為

r! / [(k1)! (1!)k1 × ... (kr)! (r!)kr]    (5)

上述結果跟《點算的奧秘:集合劃分問題》中的公式(9)完全相同。至此 我們有兩個方法計算P(k1, ... kr),我們可以借助「求Br,n的母函數」 (即公式(3))間接求這個數,也可用公式(5)直接求這個數。

接下來我們便可以綜合運用本節以及前面數節所曾介紹的方法來解決「帶異質限制條件的集合劃分」問題。以 下用一個例題來說明解題方法。

例題2:現要把6個元素劃歸2個(無序)非空子集,並規定其中一個子集至少包含3個元素,另一個子集 最多包含4個元素,問有多少種不同的「(無序)劃分」方案?

答2:本題就是《點算的奧秘:集合劃分問題的母函數》中的問 題A。在該網頁中,筆者曾指出本題的「異質限制條件」令我們的「母函數」方法失效,現在我們嘗試循另一思 路解答本題。

我們可以把解答本題的程序分成兩步。在第一步,我們暫不理會把哪些元素放入哪個子集的問題,而只考慮每 個子集應包含多少個元素的問題。這實際上等同於求解以下這個「整數分割」問題:現要把6分割為2個部分, 其中一部分不小於3,另一部分不大於4。試列出所有「分割」方案。

請注意上述「整數分割」問題跟筆者在前面數節介紹過的「整數分割」問題很不相同。不過由於現在我們的目 的是「列舉」所有符合條件的「分割」方案而非「計算」這些方案的數目,我們可不妨用以下這個「列舉型母 函數」來求解:

(N3x3 + N4x4 + N5x5 + ...) × (N1x + N2x2 + N3x3 + N4x4)

容易看到上式展開式中x6項的「系數」為

N32 + N2N4 + N1N5

上述3個「分割」方案:3+3、2+4和1+5其實代表每個子集所應包含元素個數的3種不同方案。有了上述3個方案 ,我們便可以進行解題程序的第二步,應用前面求解「規定子集元素個數的集合(無序)劃分」問題的方法來找 出符合本題限制條件的所有「(無序)劃分」方案。把n = 2代入公式(3)

(N1x + N2x2/2! + N3x3/3! ...) × (N1x + N2x2/2! + N3x3/3! ...) / 2!

根據前面的討論,本題答案就是上式展開式中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的合理性。

註1:這條算式的「求和變項」為r、k1 ... kr。由於n不是求和變和之一,n!在這裡 等於一個「常數」,因此可以「穿透」兩重Σ符號,進入算式的內層,其情況就像以下等式中的n那樣:
[a × (b + c) + d × (e + f)] / n = a × (b/n + c/n) + d × (e/n + f/n)


註2:其實我們還可以把公式(3)進一步推廣為「求Br,n的二元指數母函數」:
Σ0 ≤ k < ∞ [y(N1x + N2x2/2! + N3x3/3! ...)]k / k!
Br,n就是上式展開式中xryn / r!項的「系數」。不過在實際應用上,使 用公式(3)會更為簡單直接,所以本網頁不詳細討論這種「二元母函數」。

註3:請注意N1、N2 ...在公式(3)中是作為「不定項」而非「系數」,因此公式(3)是 「點算型母函數」,而非「列舉型母函數」。

註4:請注意在一般情況下,如果我們用「組合問題的列舉型母函數」求解「整數分割」問題,我們會得到重覆 的答案。舉例說,對於「把6分割為2個部分,各部分不小於1且不大於4」的問題,如果我們用以下「母函數」 來求解,
(N1x + N2x2 + N3x3 + N4x4)2
所得x6項的「系數」中將包含2N2N4,即把2+4這個「分割」方案重覆計算 了兩次。不過,對於「列舉型整數分割」問題來說,這不構成很大問題,只要略去那個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?us1490898632" 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>