點算的奧秘:二元母函數


點算的奧秘:整數分割問題中,筆者指出「整數分割」問題可以有兩類 限制條件:(1) 對各部分大小的限制條件;(2) 對部分個數的限制條件。在上兩節,筆者分別介紹了如何用「 母函數」方法來解決帶有這兩類限制條件的「整數分割」問題。現在的問題是,如果一個「整數分割」問題同 時帶有以上兩類限制條件(例如規定共有4個部分,並且各部分不小於1和不大於3),它的「母函數」應如何表達 ?

根據筆者在點算的奧秘:費雷爾斯圖中的介紹,對於含有第(2)類限制條 件的「整數分割」問題,我們的解題方法是利用「費雷爾斯圖」把原來要求的「分割」方案轉化為它的「共軛」 方案,從而把第(2)類限制條件轉化為第(1)類限制條件。可是當某一「整數分割」問題同時帶有以上兩類限制 條件時,上述方法便失效。舉例說,設我們的問題是要把8分割為4部分,並且各部分不小於1和不大於3。利用 上述方法,我們固然可以把原有的第(2)類限制條件(即規定所求「分割」方案須包含4部分)轉化為第(1)類限制 條件(即規定所求「分割」方案的「共軛」方案的最大部分為4)。可是,對於原有的第(1)類限制條件,我們卻 無法處理,因為當我們把某「分割」方案轉化為其「共軛」方案後,原來的「分割」方案各部分大小的上、下 限並不等於其「共軛」方案各部分大小的上、下限。

造成以上困難的原因是我們以往所接觸的「母函數」都是「一元母函數」(Univariate Generating Function),即只有一組「不定項」(Indeterminate)及其「指數」的「母函數」。在「點算組合學」上,「不 定項」相當於一般數學式子中的「變項」(Variable)。例如,在以下的「普通母函數」

Σ0 ≤ r < ∞ arxr    (1)

中,x就是「不定項」。「點算組合學」把這個x稱做「不定項」而不稱做「變項」,是因為這個x不同於一般算 式中的「變項」,它實際上只是一個「佔位符號」(Place-Holder),其作用只是純粹用來連接「系數」 ar和「指數」r,而沒有任何計算意義(註1)。跟「不定項」不同,「母函數」中的「指數」則有重 要意義,它代表「點算組合學」問題的一個「參數」(Parameter)。舉例說,假如上式(1)代表某「組合」問題, 那麼r通常代表被抽出來的物件的數目,例如a7便是抽取7個物件出來的各種「組合」方案總數。

在前面各節,當我們用「母函數」代表某「點算組合學」問題時,有關「母函數」都只有一個「參數」,因而 都表現為「一元母函數」。可是對於同時帶有上述兩類限制條件的「整數分割」問題,我們需要使用兩個「參 數」,把有關問題表達為「二元母函數」(Bivariate Generating Function)。在這兩個「參數」中 ,一個體現部分的個數,另一個則體現各部分的大小。在以下例題中,我們將使用「二元母函數」解答有關問 題。

例題1:現要把8分割為4部分,並且各部分不小於1和不大於3,問有多少種不同分割法?

答1:我們可以把這個問題重新表述為以下問題:

把4個不小於1且不大於3的整數加在一起,並且相加等於8,問有多少種不同方案?

請注意,如果略去上句中的「並且相加等於8」,餘下的部分便相當於:從1、2和3這3類數字中可重覆地抽4個 出來,問有多少種不同抽法(註2)?這其實是一個與本題相關的「組合」問題,因此我們首先考慮這個相關「組 合」問題。應用筆者在點算的奧秘:普通母函數中介紹過的方法,可以把 上述相關「組合」問題表達為以下「一元母函數」:

(1 + y + y2 + ...) × (1 + y + y2 + ...) × (1 + y + y2 + ...)

以上「一元母函數」的展開式中y4項的「系數」就是從上述3類數字中可重覆地抽4個出來的「組合 」方案總數,也就是把4個不小於1且不大於3的整數組合在一起的各種「組合」方案的總數。

請注意以上「一元母函數」中的三個「括弧」的內容完全相同,它只告訴我們共有3類數字,而沒有告訴我們這 些數字是甚麼,因此不可能用上式來求出「把4個不小於1且不大於3的整數組合在一起,並且相加等於8」的方 案總數。換句話說,上式欠缺了各數字相加之和的信息。為了把此一信息加入「母函數」中,我們須對上式的 三個「括弧」作出修改,使它們能體現所代表的數字。具體地說,我們分別用xy、x2y和 x3y代替上式中三個「括弧」中的y,使第一、第二和第三個「括弧」能分別體現它們所代表的3個 數字1、2、3。經修改後,上式變為

[1 + xy + (xy)2 + ...] × [1 + x2y + (x2y)2 + ...] × [1 + x3y + (x3y)2 + ...]    (2)

上式就是我們要求的「二元母函數」,它包含兩個「不定項」x和y,它們的「指數」就是這個「母函數」的兩 個「參數」。把上式展開後,x的「指數」就代表各部分相加之和,而y的「指數」則代表部分個數。由於本題 規定應有4個部分,並且各部分相加之和為8,本題答案就是上式展開式中x8y4項的「 系數」。以下我們憑觀察找出所求的「系數」。請注意由於我們所求的項x8y4包含兩 個「指數」,在計算時我們必須同時考慮這兩個數字,這就是「二元母函數」與「一元母函數」的差異所在。

根據觀察,當上式三個「括弧」分別取以下的項時,相乘便會得到x8y4:1, (x2y)4, 1; xy, (x2y)2, x3y; (xy)2, 1, (x3y)2。由於共有3組這樣的項,故本題答案為3。□

把上例的「母函數」加以推廣,便可以用來解決一般的同時帶有上述兩類限制條件的「整數分割」問題。設我 們要把整數r分割為n個部分,其中規定各部分不小於m和不大於M,那麼相關的「點算型二元母函數」 就是

[1 + xmy + (xmy)2 + ...] × [1 + xm+1y + (xm+1y)2 + ...] × ... [1 + xMy + (xMy)2 + ...]    (3)

上式展開式中xryn項的「系數」就是我們要求的答案。對於「列舉型整數分割問題」 ,我們可以把代表整數1、2 ... 的N1、N2 ... 等加入上式中,從而得到以下的 「列舉型二元母函數」

[1 + Nmxmy + (Nmxmy)2 + ...] × [1 + Nm+1xm+1y + (Nm+1xm+1y)2 + ...] × ... [1 + NMxMy + (NMxMy)2 + ...]    (4)

同樣,上式展開式中xryn項的「系數」提供了相關的「列舉型整數分割問題」的解答。

例題2:現要把8分割為4個部分,並且各部分不小於1和不大於3,試列出各種分割法。

答2:本題是例題1的延續。如前所述,只需把N1、N2和N3加入 上面的算式(2),便可得到本題的「列舉型二元母函數」:

[1 + N1xy + (N1xy)2 + ...] × [1 + N2x2y + (N2x2y)2 + ...] × [1 + N3x3y + (N3x3y)2 + ...]

本題答案就是上式展開式中x8y4項的「系數」。由於我們已有例題1的答案,易知所求 「系數」為:

N24 + N1N22N3 + N12N32

上式的各項代表8的某個「分割」方案。例如,N24便代表2+2+2+2,其餘照此類推。□

本節介紹的「二元母函數」雖然是為了解決同時帶有上述兩類限制條件的「整數分割」問題而提出的,但也可 用來解決只帶上述其中一類限制條件或不加任何限制條件的「整數分割」問題。換句話說,現在我們有兩種方 法來解決前兩節介紹的「整數分割」問題。以下我們用本節介紹的「二元母函數」來重新解決前兩節的某些例 題,比較兩種方法的異同。

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

答3:本題就是點算的奧秘:費雷爾斯圖中的例題2。根據該題 的解答,本題實際等同於:求把8分割成3個部分的所有「分割」方案。由然本題沒有對各部分的大小作出限制 ,因此在理論上,本題的「二元母函數」應是一個無窮乘積;但在實際上,我們只需考慮這個無窮乘積中的有 限個項。以下就是本題的「列舉型二元母函數」:

[1 + N1xy + (N1xy)2 + ...] × [1 + N2x2y + (N2x2y)2 + ...] × [1 + N3x3y + (N3x3y)2 + ...] ×
[1 + N4x4y + (N4x4y)2 + ...] × [1 + N5x5y + ...] × [1 + N6x6y + ...] × ...

本題答案就是上式展開式中x8y3項的「系數」。根據觀察(或者使用電腦軟件),這個 「系數」是

N2N32 + N22N4 + N1N3N4 + N1N2N5 + N12N6

上式的5項代表本題的5個解。例如,N2N32便代表「從其中一類物件中抽2 個出來,並從其餘兩類物件中各抽3個出來」,其餘照此類推。請注意本題答案跟上述網頁例題2的解答完全一 致,而且我們可以直接從上述「系數」中的各項得到我們要求的答案,而無須把它們轉換為其「共軛」方案。 □

例題4:現要把10分割為若干個不大於8的偶數之和,並且規定最少要有1個2和最多只可有3個2。試列 出所有「分割」方案。

答4:本題就是點算的奧秘:整數分割問題中的例題3。由於本 題規定各部分為不大於8的偶數,並且對2的出現次數作出限制,本題的「列舉型二元母函數」為:

[N2x2y + (N2x2y)2 + (N2x2y)3] × [1 + N4x4y + (N4x4y)2 + ...] × [1 + N6x6y + ...] × [1 + N8x8y + ...] × ...

請注意上式跟上述網頁答3中的「母函數」非常相似。事實上,只要把上式中的所有y略去,上式便與上述網頁 答3中的「母函數」完全一樣。由此可見,前面兩節介紹的「母函數」其實是本節介紹的「二元母函數」的特例 (註3)。由於本題沒有規定要把10分割成多少個部分,我們可以把上式中的y當作「常數」(Constant)處理。本 題答案可以從上式展開式中x10項的「系數」得到:

N2N8y2 + N2N42y3 + N22N6y3 + N23N4y4

以上「系數」的每一項由兩部分相乘而成:Ni項和yj項,前者代表我們要求的「分割」 方案,後者的指數j則代表該方案所含的部分個數,例如最後一項中的 N23N4便代表「分割」方案2+2+2+4,y4則告訴我們這個「分 割」方案包含4個部分。請注意以上答案不僅提供了符合本題規定的4個「分割」方案,而且還告訴我們這些方 案在部分個數上的分佈,即有1個「分割」方案包含2個部分,2個「分割」方案包含3個部分和1個「分割」方案 包含4個部分。□

上題的解答亦給予我們一個啟示:當「整數分割」問題沒有對某一「參數」作出規定時,我們可以把「二元母 函數」中代表該「參數」的「不定項」當作「常數」處理。 例如,以上例題沒有對「部分個數」作出規定,因 此我們在展開上述「二元母函數」時,把y當作「常數」處理。以下我們看一個須把x當作「常數」處理的例子 。

例題5:從2、4、6這3個數字中可重覆地抽3個出來相加,可構成哪些整數?

答5:由於本題只考慮3個數字,所以本題的「二元母函數」由3個「括弧」組成:

[1 + N2x2y + (N2x2y)2 + ...] × [1 + N4x4y + (N4x4y)2 + ...] × [1 + N6x6y + (N6x6y)2 + ...]

由於本題沒有規定要抽出來的3個數字相加之和是多少,我們可以把上式中的x當作「常數」 處理。本題答案可 以從上式展開式中y3項的「系數」得到:

N23x6 + N22N4x8 + (N2N42 + N22N6)x10 + (N43 + N2N4N6)x12 + (N42N6 + N2N62)x14 + N4N62x16 + N63x18

為方便以下討論,筆者把以上「系數」中各項按x的冪次歸類並按遞增序排列。以上答案顯示,用上述3個數字 可構成7個整數:6、8、10、12、14、16、18。上式還顯示各個整數符合本題規定條件的「分割」方案,例如10 便既可分割為2+4+4,又可分割為2+2+6。□

以上幾個例題顯示,前面兩節介紹的「整數分割」問題都可以用「二元母函數」解決,而且「二元母函數」還 可以解決前面兩節介紹的「一元母函數」所不能解決的問題。那麼「一元母函數」是否有其價值?筆者認為, 雖然「一元母函數」的解題能力只是「二元母函數」的的解題能力的子集,但當我們要解決的問題只含有一個 「參數」時,利用「一元母函數」來解題一般會較為簡單直接,因此「一元母函數」仍是有價值的。

在結束本節前,筆者想解釋一下,為何直至現在才介紹「二元母函數」,而在以往介紹「組合」問題和「排列」 問題的「母函數」方法時,卻只使用「一元母函數」?答案是某些「整數分割」問題包含兩個「參數」:部分 個數和各部分相加之和,因而需要使用「二元母函數」;而「組合」和「排列」問題卻一般只包含一個「參數」 ,因而只需使用「一元母函數」便足夠了。請注意,是「組合」和「排列」問題的表述方法限制了它們只有一 個「參數」,例如典型的「組合」問題一般採取以下形式:

從A、B、C這3類物件中可重覆地抽r個出來,問有多少種不同抽法?

在上述問題中,由於明確道出了物件類別的名稱(A、B、C),它限制了物件類別的數目必須是3,不能變化,因 此只有r (即被抽出來的物件數目)才可能是上述問題的「參數」。

當然我們總能構造含有兩個「參數」的「組合」和「排列」問題。

例題6:試求以下「組合」問題的「二元母函數」,並用它來求n = 3,r = 5時的值:

從n類物件(用O1 ... On代表)中可重覆地抽r個出來,問有多少種不同抽法?

答6:在上述問題中,n和r都是可變化的,因此本題含有兩個參數,現在讓我們推導本題的「二元母 函數」。根據點算的奧秘:普通母函數,當上述問題中的n等於一個確定 的值k時,相關的「一元母函數」為

(1 + x + x2 + ... )k

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

Σ1 ≤ k < ∞ [y(1 + x + x2 + ... )]k = Σ1 ≤ k < ∞ [y / (1 − x)]k

上式展開式中xryn項的「系數」就是上述「組合」問題的答案。現在讓我們求 x5y3項的「系數」。容易看到,所求答案就是[y / (1 − x)]3中 x5y3項的「系數」,亦即(1 − x)−3中x5項的「 系數」。根據點算的奧秘:普通母函數中的公式(10),這個數正是

C(3 + 5 − 1, 5) = 21

C(3 + 5 − 1, 5)正是以前介紹過的從3類物件中可重覆地抽5個出來的抽法總數的計算公式。□

類似地,對於以下「排列」問題:

從n類物件(用O1 ... On代表)中可重覆地抽r個出來排列,問有多少種不同排 法?

我們也可推導相應的「二元母函數」如下:

Σ1 ≤ k < ∞ [y(1 + x + x2/2! + ... )]k = Σ1 ≤ k < ∞ (yex)k

上式展開式中xryn / r!項的「系數」就是上述「排列」問題的答案。

註1:在「點算組合學」上,我們從來不會把數字代入「不定項」x中。

註2:有些讀者看到這裡,可能感到奇怪,筆者在點算的奧秘:分配問題 的表2中明明說「整數分割」問題對應於「抽象組合」問題,因此本題不是應等同於以下「抽象組合」問題嗎: 現要從4類沒有固定編號的物件中抽8個出來,並且須從每類物件中抽取不少於1個和不多於3個,問有多少種不 同抽法?為何現在又把本題跟「組合」問題聯繫起來?請注意,上述聯繫是在撇除「並且相加等於8」這個條件 的情況下才成立的。如果不撇除這個條件,本題所對應的只能是前述的「抽象組合」問題。

註3:事實上可以證明,當本節的「二元母函數」中的其中一個「不定項」的「指數」取定某特定數值時,便可 以把「二元母函數」轉化為本網站以前曾介紹過的「一元母函數」。但由於證明過程需用到本網站尚未介紹的 「遞歸關係」,故此本網頁略去有關證明。



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