點算的奧秘:費雷爾斯圖


點算的奧秘:整數分割問題中,筆者討論了最基本以及含有第(1)類限 制條件的「整數分割」問題。本網頁將討論含有第(2)類限制條件的「整數分割」問題。第(2)類限制條件是指 對被分割出來的部分個數的限制條件,最常見的情況是規定把正整數r分割為剛好n個部分。在「點算組合學」 上,一般把符合這類條件的「分割」方案總數記為p(r, n)。請注意我們不能直接應用上述網頁的公式(3)求解 p(r, n),因為在公式(3)中,各個「括弧」代表各部分的大小而非部分的個數。為了求解p(r, n),我們必須應 用新的方法。為此,筆者首先介紹「費雷爾斯圖」(Ferrers Diagram)的概念。

「費雷爾斯圖」是表達「整數分割」方案的形像化方法,它用r個符號(例如☉)代表整數r,並根據r的「分割」 方案把這些☉排成若干行,行的數目代表部分的個數,每行中☉的數目則代表該部分的大小。舉例說, 2+2+2+4+5+5 = 20便可以表達為下面的圖1:

☉ ☉             
☉ ☉ ☉ ☉
☉ ☉ ☉ ☉ ☉
☉ ☉ ☉ ☉ ☉ ☉ ☉
☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉
☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉
圖1 圖2

把圖1按逆時針方向旋轉90度並翻轉,便會得到圖2。圖2代表20的另一個「分割」方案:2+3+3+6+6,「點算組 合學」把上述兩個可以互相轉化的「分割」方案稱為「共軛分割」(Conjugate Partition)。利用「 共軛分割」,我們可以解決很多「整數分割」問題。在介紹這些解題方法前,我們首先找出如何在一對「共軛 分割」之間進行轉換,而不用繪出其「費雷爾斯圖」。我們先從一個簡單的例子開始。

例題1:給定17的一個「分解」方案2+2+2+4+5+5,試求與其「共軛」的另一個「分解」方案。

答1:為方便以下的推導,以下用指數代表某整數在「分解」方案中出現的次數。這樣本題給定的「 分解」方案便可寫成(2)3(4)(5)2。雖然我們希望不用繪出「費雷爾斯圖」便能找到答 案,但是觀看上面的圖1和圖2對找出這對「共軛分割」之間的關係仍是有益的。

比較該兩幅圖,便會發現某一方的行數正好等於另一方最底一行所含☉的數目,例如圖1共有6行,而圖2最底一 行恰有6個☉。讀者應不難發現,此一關係不是偶然的,即某一「分解」方案的部分個數必然等於其「共軛」方 案的最大部分。由於給定的「分解」方案(2)3(4)(5)2含有6個部分(這個6可由把各項 的指數相加而得,不要忘記4的指數是1),所以可以斷定其「共軛」方案的最大部分必然是6。

確定了這個6,我們便可以把它從我們的「分解」方案中撇除,集中處理餘下的部分。這對於圖1和圖2來說,相 當於分別刪除該圖中最左的一列和最底的一行,從而得到以下兩圖:

             
 ☉ ☉
 ☉ ☉ ☉
☉ ☉ ☉ ☉ ☉ ☉
☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉ ☉
☉ ☉ ☉ ☉  
圖3 圖4

比較一下圖3所對應的「分解」方案(1)3(3)(4)2與原來的「分解」方案 (2)3(4)(5)2,便會發現從圖1中刪除最左一列相當於把原來的「分解」方案中各項的 「底數」減1 (「指數」則維持不變)。由於(1)3(3)(4)2各項指數之和為6,所以可以 斷定,所求的「共軛」方案中的倒數第二個部分必然是6。接著我們也把這個6也撇除。

把這第二個6撇除後,我們的「分解」方案便變成(2)(3)2。請注意這也是把 (1)3(3)(4)2中各項的「底數」減1的結果(由於1 − 1 = 0,我們不再把它寫出 來)。由於(2)(3)2各項指數之和為3,所以可以斷定,所求的「共軛」方案中的倒數第三個部分必 然是3。

把剛才確定的3撇除後,我們的「分解」方案便變成(1)(2)2。由於(1)(2)2各項指數之 和為3,所以可以斷定,所求的「共軛」方案中的倒數第四個部分必然是3。

把剛才確定的3撇除後,我們的「分解」方案便變成(1)2。由於(1)2各項指數之和為2 ,所以可以斷定,所求的「共軛」方案中的倒數第五個部分必然是2。請注意完成了這一步,我們便無須繼續下 去,因為把剛才確定的2也撇除後,我們的「分解」方案便再沒有數字了。至此我們確定所求的「共軛」方案為 (2)(3)2(6)2。□

我們可以把上述計算過程推廣到一般的情況。給定一個「分解」方案

(n1)i1(n2)i2 (n3)i3...(nk)ik    (1)

其中i1 + i2 + i3 + ... ik = n,讓我們找出它的「共軛」 方案。如前所述,某一「分解」方案的部分個數必然等於其「共軛」方案的最大部分。由於以上「分解」方案 的部分個數就是其「指數」之和,可以推斷所求「共軛」方案的最大部分必然是n。

接著我們撇除這個n,這相當於把(1)中各項的「底數」減1 (「指數」則維持不變)。這時有兩個可能性:(a) n1 − 1 > 0和(b) n1 − 1 = 0。先考慮情況(a)。在這情況下,(1)變成

(n1 − 1)i1 (n2 − 1)i2 (n3 − 1)i3... (nk − 1)ik    (2)

由於上式中各項「指數」之和仍然是n,可以推斷所求「共軛」方案的倒數第二部分必然也是n,即有至少兩個n 。接著我們又撇除這個n,即把(2)中各項的「底數」減1,即相當於把(1)中各項的「底數」減2。假如所得結果 仍不為0,那麼可以推斷,所求「共軛」方案的倒數第三部分必然也是n ...

由於n1是有限數,當它被減n1次後,便會等於0,因此我們終會碰到上述的情況(b)。 在這情況下,(1)變成

(n2 − n1)i2 (n3 − n1)i3... (nk − n1)ik    (3)

由於上式較(1)少了一項,各項「指數」之和不會再是n,所以可以推斷,所求「共軛」方案的倒數第 n1 + 1部分不再是n。但由於在此之後的部分全部都是n,可以推斷,在所求「共軛」方案中, n的指數必然是n1

接著我們繼續研究上面的式(3)。容易看到,這個式子各項「指數」之和是i2 + i3 + ... ik = n − i1,所以可以推斷,在所求「共軛」方案中,比n次小的 部分必然是n − i1

接著我們仿照前面的做法,把剛才確定的n − i1撇除,這相當於把(3)中各項的「底 數」減1。同樣,當這個過程進行n2 − n1次後,式(3)中的第一項便會消失。但 在它消失之前,每次各項「指數」之和都是n − i1。由此可以推斷,在所求「共軛」 方案中,n − i1的指數必然是n2 − n1

請注意當式(3)中各項的「底數」被減去n2 − n1後,該式便變成

(n3 − n2)i3... (nk − n2)ik    (4)

上式中各項「指數」之和是i3 + ... ik = n − i1 − i2。由此可以推斷,在所求「共軛」方案中,比n − i1次小的部 分必然是n − i1 − i2,並且仿照前面的推理,可知 n − i1 − i2的指數必然是n3 − n2

我們可以把以上推理繼續進行下去,直至原來「分割」方案的所有項皆被減去為止。這樣我們便得到式(1)的「 共軛」方案:

(ik)nk − nk−1 ... (n − i1 − i2)n3 − n2 (n − i1)n2 − n1 (n)n1    (5)

推導了一對「共軛分割」之間的轉化關係,我們便繼續推導p(r, n)的「母函數」。如前所述,某一「分割」方 案的部分個數剛好等於其「共軛」方案的最大部分,所以我們可以把對「分割」方案中部分個數的限制轉化為 對其最大部分的限制。由於p(r, n)等於把r分為n個部分的「分割」方案總數,這個數等於最大部分為n的r的「 分割」方案總數。有些讀者可能以為,由於各部分不大於n,根據點算的奧秘: 整數分割問題中的公式(3),所求的「母函數」似乎是

(1 + x + x2 + ...) × (1 + x2 + x4 + ...) × ... (1 + xn + x2n + ...)    (6)

可是上式不是我們要求的「母函數」,因為上式只代表「分割」方案中的最大部分可能為n,但並不保 證最大部分實際為n。舉例說,我們可以從上面第1個「括弧」抽取xr,並從所有其他「括 弧」抽取1,相乘結果為xr。上述結果代表把r分割成r個1,其最大部分只是1而非r。由此可見,上 式只代表把r分割成最多n個(而非剛好n個)部分的「分割」方案總數(註1)。

為了保證我們的「母函數」真正代表p(r, n),必須對上式最後一個「括弧」略作修改。由於我們要確保最大部 分實際為n,「分割」方案必須包含至少1個n。這樣我們只需從上式最後一個「括弧」中剔除1 (即不容 許沒有n),便得到「求p(r, n)的母函數」

 (1 + x + x2 + ...) × (1 + x2 + x4 + ...) × ... (xn + x2n + x3n + ...)
=xn × (1 + x + x2 + ...) × (1 + x2 + x4 + ...) × ... (1 + xn + x2n + ...)    (7)

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

如果我們把代表整數1、2 ...的符號N1、N2 ...加入上式中,便得到以下的「列舉型 母函數」:

Nnxn × [1 + N1x + (N1x)2 + ...] × [1 + N2x2 + (N2x2)2 + ...] × ... [1 + Nnxn + (Nnxn)2 + ...]    (8)

惟請注意,上式展開式中xr項的「系數」其實是「最大部分為n」的r的所有「分割」方案。如果我 們應用公式(5),把這些「分割」方案逐一轉換成其「共軛」方案,便會得到「含有n個部分」的r的所有分割方 案。

例題2:現要從3類沒有固定編號的物件中抽取8個出來,並規定必須從每類物件中至少抽一個出來。 試列出所有不同抽法。

答2:這個問題就是點算的奧秘:分配問題中介紹的「抽象組合 」問題。根據該網頁的表2,這類問題對應於「整數分割」問題。因此本題實際等同於:求把8分割成3個部分的 所有「分割」方案。把n = 3代入公式(8),便得到本題的「母函數」為

N3x3 × [1 + N1x + (N1x)2 + + ...] × [1 + N2x2 + (N2x2)2 + ...] × [1 + N3x3 + (N3x3)2 + ...]

本題答案就是上式展開式中x8項的「系數」,即

N2N32 + N1N22N3 + N12N32 + N13N2N3 + N15N3

接著我們把上式中的N1、N2、N3改寫為(1)、(2)、(3),然後對上面5個項 逐一應用公式(5)(或繪出其「費雷爾斯圖」),把它們轉換為其「共軛」方案:

(2)(3)2, (1)(3)(4), (2)2(4), (1)(2)(5), (1)2(6)

最後,我們還得應用「整數分割」問題與「抽象組合」問題之間的對應關係把以上5項「翻譯」為我們要求的答 案。所求的5個「抽象組合」方案為:

(1)從其中一類物件中抽2個出來,並從其餘兩類物件中各抽3個出來
(2)從其中一類物件中抽1個出來,從第二類中抽3個出來,從第三類中抽4個出來
(3)從其中兩類物件中各抽2個出來,並從最後一類中抽4個出來
(4)從其中一類物件中抽1個出來,從第二類中抽2個出來,從第三類中抽5個出來
(5)從其中兩類物件中各抽1個出來,並從最後一類中抽6個出來

請注意在上述答案中,「其中一類」、「第二類」、「最後一類」等字眼都只是這三類物件的「臨時編號」, 並不代表某種既定的次序。因此之故,上述5個方案中的每一個都可重新表述為等價的形式,例如方案(2)便可 以重新表述為「從其中一類物件中抽3個出來,從第二類中抽1個出來,從第三類中抽4個出來」或「從其中一類 物件中抽4個出來,從第二類中抽3個出來,從第三類中抽1個出來」,以上不同表述法其實都表達同一個意思。 □

巧妙地運用前面介紹的公式,我們還可以解決某些包含較複雜限制條件的「整數分割」問題。

例題3:現要把6分割成最少3個和最多5個部分,問有多少種不同分割法?

答3:利用前面的公式(6),可以求得把6分割成最多5個部分的「分割」方案總數。可是公式(6)只能 用於「最多n個部分」的問題,不適用於「最少n個部分」的問題。不過我們可以利用「集合論」解決這個問題 。我們可以把6的所有「分割」方案看成一個集合,並按「分割」方案所含部分個數把這個集合劃分為6個子集 :包含1個部分的「分割」方案...包含6個部分的「分割」方案,分別稱為A1 ... A6 。有了以上的定義,我們便可以確定以下3個集合:

包含最多5個部分的「分割」方案:A1 ∪ A2 ∪ A3 ∪ A4 ∪ A5
包含最多2個部分的「分割」方案:A1 ∪ A2
包含最少3個和最多5個部分的「分割」方案:A3 ∪ A4 ∪ A5 ∪ A5

顯然本題所要求的「分割」方案(即上面的第三式)就是上面的第一式減去第二式,而第一和第二式都是「最多n 個部分」的問題,因此都可以用公式(6)求解。

計算方法之一是分別把n = 5和n = 2代入公式(6),找出兩個展開式中x6項的「系數」,然後相減 。此一做法無疑是正確的,但卻會浪費某些計算工夫(除非是使用電腦軟件)。一個較簡捷的方法是只把n = 5代 入公式(6),得到

(1 + x + x2 + x3 + x4 + x5 + x6 + ...) × (1 + x2 + x4 + x6 + ...) × (1 + x3 + x6 ...) × (1 + x4 + ...) × (1 + x5 + ...)

接下來我們必須找出從上式5個「括弧」中各取出哪些項相乘會得到x6,但須捨棄那些後三個「括 弧」皆取1的組合,因為這些組合實際只由前兩個「括弧」的項組成,因此代表「包含最多2個部分」的「分割」 方案,不符合本題的限制條件。根據觀察,符合上述規定的組合包括:1, 1, x6, 1, 1; 1, x2, 1, x4, 1; x, 1, 1, 1, x5; x, x2, x3, 1, 1; x2, 1, 1, x4, 1; x3, 1, x3, 1, 1。由於共有6個這 樣的組合,故本題答案為6。□

註1:由此亦可見,把r分成不大於n的若干個部分的「分割」方案總數 = 把r分成最多n個部分的「分割」方案 總數。


返回數學專題
<!-- 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?us1490898566" 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>