在點算的奧秘:整數分割問題中,筆者指出「整數分割」問題可以有兩類限制條件:(1) 對各部分大小的限制條件;(2) 對部分個數的限制條件。在上兩節,筆者分別介紹了如何用「母函數」方法來解決帶有這兩類限制條件的「整數分割」問題。現在的問題是,如果一個「整數分割」問題同時帶有以上兩類限制條件(例如規定共有4個部分,並且各部分不小於1和不大於3),它的「母函數」應如何表達?
根據筆者在點算的奧秘:費雷爾斯圖中的介紹,對於含有第(2)類限制條件的「整數分割」問題,我們的解題方法是利用「費雷爾斯圖」把原來要求的「分割」方案轉化為它的「共軛」方案,從而把第(2)類限制條件轉化為第(1)類限制條件。可是當某一「整數分割」問題同時帶有以上兩類限制條件時,上述方法便失效。舉例說,設我們的問題是要把8分割為4部分,並且各部分不小於1和不大於3。利用上述方法,我們固然可以把原有的第(2)類限制條件(即規定所求「分割」方案須包含4部分)轉化為第(1)類限制條件(即規定所求「分割」方案的「共軛」方案的最大部分為4)。可是,對於原有的第(1)類限制條件,我們卻無法處理,因為當我們把某「分割」方案轉化為其「共軛」方案後,原來的「分割」方案各部分大小的上、下限並不等於其「共軛」方案各部分大小的上、下限。
造成以上困難的原因是我們以往所接觸的「母函數」都是「一元母函數」(Univariate Generating Function),即只有一組「不定項」(Indeterminate)及其「指數」的「母函數」。在「點算組合學」上,「不定項」相當於一般數學式子中的「變項」(Variable)。例如,在以下的「普通母函數」
中,x就是「不定項」。「點算組合學」把這個x稱做「不定項」而不稱做「變項」,是因為這個x不同於一般算式中的「變項」,它實際上只是一個「佔位符號」(Place-Holder),其作用只是純粹用來連接「系數」ar和「指數」r,而沒有任何計算意義(註1)。跟「不定項」不同,「母函數」中的「指數」則有重要意義,它代表「點算組合學」問題的一個「參數」(Parameter)。舉例說,假如上式(1)代表某「組合」問題,那麼r通常代表被抽出來的物件的數目,例如a7便是抽取7個物件出來的各種「組合」方案總數。
在前面各節,當我們用「母函數」代表某「點算組合學」問題時,有關「母函數」都只有一個「參數」,因而都表現為「一元母函數」。可是對於同時帶有上述兩類限制條件的「整數分割」問題,我們需要使用兩個「參數」,把有關問題表達為「二元母函數」(Bivariate Generating Function)。在這兩個「參數」中,一個體現部分的個數,另一個則體現各部分的大小。在以下例題中,我們將使用「二元母函數」解答有關問題。
例題1:現要把8分割為4部分,並且各部分不小於1和不大於3,問有多少種不同分割法?
答1:我們可以把這個問題重新表述為以下問題:
請注意,如果略去上句中的「並且相加等於8」,餘下的部分便相當於:從1、2和3這3類數字中可重覆地抽4個出來,問有多少種不同抽法(註2)?這其實是一個與本題相關的「組合」問題,因此我們首先考慮這個相關「組合」問題。應用筆者在點算的奧秘:普通母函數中介紹過的方法,可以把上述相關「組合」問題表達為以下「一元母函數」:
以上「一元母函數」的展開式中y4項的「系數」就是從上述3類數字中可重覆地抽4個出來的「組合」方案總數,也就是把4個不小於1且不大於3的整數組合在一起的各種「組合」方案的總數。
請注意以上「一元母函數」中的三個「括弧」的內容完全相同,它只告訴我們共有3類數字,而沒有告訴我們這些數字是甚麼,因此不可能用上式來求出「把4個不小於1且不大於3的整數組合在一起,並且相加等於8」的方案總數。換句話說,上式欠缺了各數字相加之和的信息。為了把此一信息加入「母函數」中,我們須對上式的三個「括弧」作出修改,使它們能體現所代表的數字。具體地說,我們分別用xy、x2y和x3y代替上式中三個「括弧」中的y,使第一、第二和第三個「括弧」能分別體現它們所代表的3個數字1、2、3。經修改後,上式變為
上式就是我們要求的「二元母函數」,它包含兩個「不定項」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,那麼相關的「點算型二元母函數」就是
上式展開式中xryn項的「系數」就是我們要求的答案。對於「列舉型整數分割問題」,我們可以把代表整數1、2 ... 的N1、N2 ... 等加入上式中,從而得到以下的「列舉型二元母函數」
同樣,上式展開式中xryn項的「系數」提供了相關的「列舉型整數分割問題」的解答。
例題2:現要把8分割為4個部分,並且各部分不小於1和不大於3,試列出各種分割法。
答2:本題是例題1的延續。如前所述,只需把N1、N2和N3加入上面的算式(2),便可得到本題的「列舉型二元母函數」:
本題答案就是上式展開式中x8y4項的「系數」。由於我們已有例題1的答案,易知所求「系數」為:
上式的各項代表8的某個「分割」方案。例如,N24便代表2+2+2+2,其餘照此類推。□
本節介紹的「二元母函數」雖然是為了解決同時帶有上述兩類限制條件的「整數分割」問題而提出的,但也可用來解決只帶上述其中一類限制條件或不加任何限制條件的「整數分割」問題。換句話說,現在我們有兩種方法來解決前兩節介紹的「整數分割」問題。以下我們用本節介紹的「二元母函數」來重新解決前兩節的某些例題,比較兩種方法的異同。
例題3:現要從3類沒有固定編號的物件中抽取8個出來,並規定必須從每類物件中至少抽一個出來。試列出所有不同抽法。
答3:本題就是點算的奧秘:費雷爾斯圖中的例題2。根據該題的解答,本題實際等同於:求把8分割成3個部分的所有「分割」方案。由然本題沒有對各部分的大小作出限制,因此在理論上,本題的「二元母函數」應是一個無窮乘積;但在實際上,我們只需考慮這個無窮乘積中的有限個項。以下就是本題的「列舉型二元母函數」:
本題答案就是上式展開式中x8y3項的「系數」。根據觀察(或者使用電腦軟件),這個「系數」是
上式的5項代表本題的5個解。例如,N2N32便代表「從其中一類物件中抽2個出來,並從其餘兩類物件中各抽3個出來」,其餘照此類推。請注意本題答案跟上述網頁例題2的解答完全一致,而且我們可以直接從上述「系數」中的各項得到我們要求的答案,而無須把它們轉換為其「共軛」方案。
□
例題4:現要把10分割為若干個不大於8的偶數之和,並且規定最少要有1個2和最多只可有3個2。試列出所有「分割」方案。
答4:本題就是點算的奧秘:整數分割問題中的例題3。由於本題規定各部分為不大於8的偶數,並且對2的出現次數作出限制,本題的「列舉型二元母函數」為:
請注意上式跟上述網頁答3中的「母函數」非常相似。事實上,只要把上式中的所有y略去,上式便與上述網頁答3中的「母函數」完全一樣。由此可見,前面兩節介紹的「母函數」其實是本節介紹的「二元母函數」的特例(註3)。由於本題沒有規定要把10分割成多少個部分,我們可以把上式中的y當作「常數」(Constant)處理。本題答案可以從上式展開式中x10項的「系數」得到:
以上「系數」的每一項由兩部分相乘而成: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個「括弧」組成:
由於本題沒有規定要抽出來的3個數字相加之和是多少,我們可以把上式中的x當作「常數」 處理。本題答案可以從上式展開式中y3項的「系數」得到:
為方便以下討論,筆者把以上「系數」中各項按x的冪次歸類並按遞增序排列。以上答案顯示,用上述3個數字可構成7個整數:6、8、10、12、14、16、18。上式還顯示各個整數符合本題規定條件的「分割」方案,例如10便既可分割為2+4+4,又可分割為2+2+6。□
以上幾個例題顯示,前面兩節介紹的「整數分割」問題都可以用「二元母函數」解決,而且「二元母函數」還可以解決前面兩節介紹的「一元母函數」所不能解決的問題。那麼「一元母函數」是否有其價值?筆者認為,雖然「一元母函數」的解題能力只是「二元母函數」的的解題能力的子集,但當我們要解決的問題只含有一個「參數」時,利用「一元母函數」來解題一般會較為簡單直接,因此「一元母函數」仍是有價值的。
在結束本節前,筆者想解釋一下,為何直至現在才介紹「二元母函數」,而在以往介紹「組合」問題和「排列」問題的「母函數」方法時,卻只使用「一元母函數」?答案是某些「整數分割」問題包含兩個「參數」:部分個數和各部分相加之和,因而需要使用「二元母函數」;而「組合」和「排列」問題卻一般只包含一個「參數」,因而只需使用「一元母函數」便足夠了。請注意,是「組合」和「排列」問題的表述方法限制了它們只有一個「參數」,例如典型的「組合」問題一般採取以下形式:
在上述問題中,由於明確道出了物件類別的名稱(A、B、C),它限制了物件類別的數目必須是3,不能變化,因此只有r (即被抽出來的物件數目)才可能是上述問題的「參數」。
當然我們總能構造含有兩個「參數」的「組合」和「排列」問題。
例題6:試求以下「組合」問題的「二元母函數」,並用它來求n = 3,r = 5時的值:
答6:在上述問題中,n和r都是可變化的,因此本題含有兩個參數,現在讓我們推導本題的「二元母函數」。根據點算的奧秘:普通母函數,當上述問題中的n等於一個確定的值k時,相關的「一元母函數」為
當k的值變化時,上式便會隨之而變化。現在只要我們把上式乘以yk,並對k求和,便得到要求的「二元母函數」:
上式展開式中xryn項的「系數」就是上述「組合」問題的答案。現在讓我們求x5y3項的「系數」。容易看到,所求答案就是[y / (1 − x)]3中x5y3項的「系數」,亦即(1 − x)−3中x5項的「系數」。根據點算的奧秘:普通母函數中的公式(10),這個數正是
C(3 + 5 − 1, 5)正是以前介紹過的從3類物件中可重覆地抽5個出來的抽法總數的計算公式。□
類似地,對於以下「排列」問題:
我們也可推導相應的「二元母函數」如下:
上式展開式中xryn / r!項的「系數」就是上述「排列」問題的答案。
註1:在「點算組合學」上,我們從來不會把數字代入「不定項」x中。