筆者在《點算的奧秘:分配問題》中介紹了兩種「整數分割」問題:「整數有序分割」問題和「整數(無序)分割」問題。它們分別對應著兩種「分配」問題和「組合」問題(參見上述網頁的表2)。由於「整數有序分割」問題對應著我們熟知的「組合」問題,「組合」問題的所有定理、公式、解題技巧都可應用於「整數有序分割」問題,本網頁不考慮這種「整數分割」問題,因此如無特別註明,本網頁討論的「整數分割」問題都是指「整數(無序)分割」問題。
「整數分割」問題是指以下問題:現要把正整數r分割為若干個(沒有固定次序的)非負整數(稱為「部分」Part)相加之和,問有多少種不同分割法?由於各部分無次序之分,以下我們規定在列出某個正整數的各部分時,把它們按遞增序排列。正如以前介紹的各類「點算組合學」問題一樣,「整數分割」問題可以按照添加於其上的各種限制條件而分為多種類別。這些限制條件可分為兩大類:
(1) | 對各部分大小的限制條件(例如規定各部分的上、下限) |
(2) | 對部分個數的限制條件(例如規定把r分割為n個部分) |
特別地,在「點算組合學」上一般規定各部分的下限為1 (註1)。因此在以下討論中,如無特別註明,我們的「整數分割」問題都是各部分下限為1的「整數分割」問題,即我們只考慮把r分割為若干個正整數相加之和的問題。在「點算組合學」上,一般把r的「分割」方案總數記為p(r)。
筆者在《點算的奧秘:分配問題》中曾指出,我們不能單靠以往介紹的方法(例如「容斥原理」),而必須運用新的方法來解決「整數分割」問題,前數節介紹的「母函數」方法就是這種新方法。事實上,我們無法用一條公式來表達p(r)的值。為方便以後的討論,現首先把p(r)的部分數值列於下表:
r | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
p(r) | 1 | 2 | 3 | 5 | 7 | 11 | 15 | 22 | 30 | 42 |
以下我們用「母函數」方法求p(r),即求解最簡單的,不含任何限制條件的「整數分割」問題。我們可以把這種「整數分割」問題轉化為一種我們以前處理過的問題。我們用k1、k2 ... kr分別代表在r的某一「分割」方案中所出現的1、2 ... r的個數。請注意下式是成立的:
舉例說,我們可以把17分割為1+1+1+2+2+4+6。在這個「分割」方案中,k1 = 3,k2 = 2,k4 = 1,k6 = 1,其餘的k3、k5、k7 ... k17通通等於0,而且3 + 2 × 2 + 4 × 1 + 6 × 1 = 17。
請注意在以上的公式(1)中,k1、k2 ... kr有次序之分(例如k1 = 0、k2 = 1與k2 = 0、k1 = 1便代表兩個完全不同的「分割」方案),而且可以取0值。這樣透過公式(1),我們把「(下限為1)的整數(無序)分割」問題轉化為「下限為0的整數有序分割」問題。而根據《點算的奧秘:分配問題》中的表2,後者對應於「組合」問題,因此我們可以利用《點算的奧秘:普通母函數》中介紹的「組合問題的母函數」(即「普通母函數」)來解決這類問題。不過在應用「母函數」方法前,我們須先把公式(1)修改為下式:
這裡既不事先規定上式包含多少個項,也不事先規定這些項相加後等於甚麼值,是因為我們希望「母函數」不僅可解決r等於某一個特定的值的問題,而是r等於任何正整數的問題。
現在讓我們把上式表達為「母函數」。我們首先把k1、2k2、3k3 ... 看成不同種類的物件,每一類物件用一個「括弧」代表。由於k1的值可以為0、1、2 ...,對應於k1的「括弧」為(1 + x + x2 + ...)。其次考慮2k2,由於2k2所取的值只能是2的倍數而非任何正整數,所以對應於2k2「括弧」為(1 + x2 + x4 + ...)。一般地,由於iki所取的值只能是i的倍數而非任何正整數,所以對應於iki「括弧」為(1 + xi + x2i + ...)。把這些「括弧」相乘後,便得到「求p(r)的母函數」:
p(r) (即r的「分割」方案總數)就是上式展開式中xr項的「系數」。有些人可能覺得奇怪,上式是一個「無窮乘積」,如何能把它展開?答案是我們不必真的把上式展開。由於在實際問題中,被分割的r總是一個有限數,在尋求xr項的「系數」時,我們實際只需考慮前r個「括弧」的乘積,而且在每個「括弧」中,只需考慮有限個項,凡是形如xs (s > r)的項都不用考慮,因為這些項與其他項相乘,不可能得出xr。以下例題顯示如何利用上方法求p(r)。
例題1:試求5的「分割」方案總數,即p(5)。
答1:本題的「母函數」為:
p(5)就是上式展開式中x5項的「系數」。我們當然可以用合適的電腦軟件展開上式並「讀取」x5項的「系數」(須先略去省略號的部分,因為電腦不懂計算「無窮乘積」),但也可以憑觀察找出要求的答案。根據觀察,在以上「無窮乘積」的頭5個「括弧」取以下數值時,相乘會得到x5項:1, 1, 1, 1, x5; 1, x2, x3, 1, 1; x, 1, 1, x4, 1; x, x4, 1, 1, 1; x2, 1, x3, 1, 1; x3, x2, 1, 1, 1; x5, 1, 1, 1, 1。由於以上7組數值的相乘結果均為x5,所以上式展開式中x5項的「系數」是7,即p(5) = 7。□
雖然我們可以把公式(3)改寫成
但由於各個「括弧」的內容不同,上式難以再作化簡,因此上式只有理論意義,並不方便計算。在實際計算p(r)時,我們還是要使用公式(3)的形式。在沒有電腦軟件的情況下,利用公式(3)求p(r)其實跟憑個人智慧找出p(r)沒有太大差別。不過正如筆者多次強調的,「母函數」為我們提供了表達某些點算問題的簡單而有系統的方法,因而是有價值的。而且「母函數」方法不僅可用來解決「點算型整數分割」問題,還能解決「列舉型整數分割」問題,其方法跟《點算的奧秘:列舉型母函數》中介紹的方法完全相同。假如我們用符號N1、N2 ...分別代表整數1、2 ...,並把這些符號加入上面的公式(3),便得到以下的「求p(r)的列舉型母函數」:
例題2:列出5的所有「分割」方案。
答2:本題是例題1的延續,因此只需把該題的「母函數」修改為下式,便可用來解答本題:
本題答案就是上式展開式中x5項的「系數」。根據例題1的解答,容易得到這個「系數」為
上式的各項代表5的某個「分割」方案。例如,N5代表1個5,N12N3則代表2個1和1個3,即1+1+3,其餘照此類推。□
接下來我們考慮帶有各種限制條件的「整數分割」問題,本網頁只討論上文提到的第(1)類限制條件,即對分割出來的各部分大小的限制條件,例如規定其上、下限,或甚至規定各部分只可包含哪些數,或某些數出現的次數。回顧前面的公式(3),每個「括弧」代表公式(2)中的某項iki,而ki則是某一「分割」方案中所出現的整數i的個數。因此,對各部分大小的限制相當於對ki的限制。以下例題顯示如何因應給定的限制條件調整公式(3)或(5),從而解題。
例題3:現要把10分割為若干個不大於8的偶數之和,並且規定最少要有1個2和最多只可有3個2。試列出所有「分割」方案。
答3:由於規定了各部分為不大於8的偶數,本題的「母函數」只包括4個「括弧」,分別代表2、4、6和8。對於每個「括弧」,我們只需考慮有限個項。特別地,本題對2的出現次數作出了限制,此一限制必須反映在代表2的「括弧」中。因此本題的「列舉型母函數」為
本題答案就是上式展開式中x10項的「系數」。根據觀察,這個「系數」是
上式的各項代表符合給定條件的4個「分割」方案。例如N23N4便代表2+2+2+4。□
例題4:現要把9分割為各不相等的部分。試列出所有「分割」方案。
答4:初看起來,本題的限制條件似乎跟前面介紹的很不相同,難以用「母函數」來表達,但其實也可以看成帶某種「上限」。規定各部分不相等,其實就等於規定在「分割」方案中,每個整數最多只能出現1次,即各個部分的「上限」為1。這樣我們便可以用前面的方法把本題的限制條件表達為「母函數」了。
由於各個部分的「上限」為1,本題的「列舉型母函數」為
本題答案就是上式展開式中x9項的「系數」。根據觀察,這個「系數」是
上式的各項代表符合給定條件的8個「分割」方案。例如N1N2N6便代表1+2+6。□
「整數分割」問題還有另一類限制條件,即上文提過的第(2)類限制條件。由於含有這類限制條件的「整數分割」問題須使用新的方法求解,這個課題將留待下節討論。
在結束本節之前,筆者想討論一下能否利用「容斥原理」求解「整數分割」問題?顯而易見,利用「容斥原理」難以解決「列舉型整數分割」問題。但即使對於「點算型整數分割」問題,我們也不能單靠「容斥原理」求解。可是本網頁以往介紹「容斥原理」時,曾指出這個原理是「點算組合學」上非常有用的解題工具。為何它對「整數分割」問題卻無能為力?在以下例題中,筆者將嘗試利用「容斥原理」求解一個包含第1類限制條件的「整數分割」問題,看看「容斥原理」在哪裡失效,從而對「容斥原理」的效用和限制有更深入的認識。
例題5:現要將12分割為若干個部分。若其中規定各部分包含最多1個1、最少1個2和1至2個3,其他整數則沒有任何限制,問有多少種分割法?
答5:本題與《點算的奧秘:帶上、下限的排列組合問題》中的例題1非常相似,現在我們仿照該網頁的解題方法用「容斥原理」解答本題。
我們用k1、k2、k3分別代表在12的某一「分割」方案中所出現的1、2、3的個數,本題的限制條件其實就是對k1、k2、k3的限制條件。現在首先把這些限制條件全部表述為「上、下限」的形式。對於k1而言,由於規定最多有1個1,所以k1的上、下限分別為1和0。對於k2而言,雖然題目沒有給定其上限,但由於12最多只能被分割為6個2,所以k2的上、下限應分別為6和1。至此我們可以把本題的限制條件表達為0 ≤ k1 ≤ 1;1 ≤ k2 ≤ 6和1 ≤ k3 ≤ 2。
現在我們首先解決「下限」的問題。由於本題規定了各部分包含最少有1個2和1個3,這實際上已確定了12的「分割」方案必有2+3,因此原來的問題已轉化為12 − (2 + 3) = 7的「分割」問題,而且原來的「下限」已完全消除,即全部轉化為0。原來的「上限」也須作出調整,由於原題規定最多只有2個3,因此在7的「分割」方案中最多只有1個3,即k3的「上限」轉化為2 − 1 = 1。同理,k2的「上限」也轉化為6 − 1 = 5。因此原題的限制條件現轉化為0 ≤ k1 ≤ 1;0 ≤ k2 ≤ 5和0 ≤ k3 ≤ 1。
現設U為7的各種不受任何限制的「分割」方案組成的集合,S1為把7分割且違反上段第一個限制條件的各種「分割」方案組成的集合,S2和S3的定義照此類推。那麼本題實際上是要求|S1' ∩ S2' ∩ S3'|,即符合所有條件的「分割」方案的總數。由於三個「上限」各不相同,S1、S2和S3不是「可交換集合」,因此本題要用以下的公式(6)求解。
我們先求|U|,|U|實際等於前面定義的p(7)。可是我們並無現成的公式計算p(7),只能參照前面的表1或使用前文介紹的「母函數」方法(或者本網站以後會介紹的「遞歸關係」方法)求這個值。至此我們看到了「容斥原理」的限制,「容斥原理」主要是用來解決一些含有限制條件的「點算組合學」問題。但如要用它來解決這些問題,我們須先能解決與該問題相關的基本(即沒有任何限制條件的)問題。對於「整數分割」問題而言,利用本網站以往介紹的方法,連最基本的問題也不能解決,這就是筆者說不能單靠「容斥原理」求解這類問題的原因。
雖然「容斥原理」有上述限制,但若把它與本網頁介紹的方法結合,仍能解決本題。現在我們就利用表1所載的結果繼續解答本題。根據表1,|U| = p(7) = 15。
接著求|S1|。這個集合中的元素違反第一個條件0 ≤ k1 ≤ 1,即有至少2個1。由於此一情況確定了在7的「分割」方案中必有1+1,它把我們的問題轉化為7 − (1 + 1) = 5的不加任何限制的「分割」問題,即求p(5)的問題,因此根據表1,|S1| = p(5) = 7。基於相同的推理,我們知道|S3| = p(7 − (3 + 3)) = p(1) = 1。接著考慮|S2|。這個集合中的元素違反第二個條件0 ≤ k2 ≤ 5,即有至少6個2。但這是不可能做到的,因此|S2| = 0。以上這三個值構成公式(6)中的S3,1,故得 S3, 1 = 7 + 1 = 8。
接著求S3, 2中各項的值,S3, 2中各項所代表的集合中的元素同時違反了上述三個條件中的兩個。根據上段的討論,不存在違反第二個條件的分割法,因此我們只需考慮同時違反第一和第三個條件的分割法,即有至少2個1和2個3。但這是不可能做到的,由此可以確定S3, 2 = 0。
接著求S3, 3,S3, 3只含有一項,即|S1 ∩ S2 ∩ S3|。由於同時違反上述三個條件是不可能做到的,因此這個集合是空集,即S3, 3 = 0。
至此,我們可以應用公式(6)求得本題答案為
請注意,我們也可用「母函數」方法解上題,但似乎不及「容斥原理」那麼簡潔。由此可見,「點算組合學」問題並無放諸四海而皆準的解題方法,我們必須靈活運用各種技巧。
註1:數學界在提到「整數分割」問題時,一般都是本網頁所指的那種「狹義」的「整數分割」問題,即各部分下限為1的「整數(無序)分割」問題,他們一般不考慮「整數有序分割」問題或容許下限為0的「整數分割」問題。本網站只是純粹出於概念完整性和對稱性的考慮,才提出較廣義的「整數分割」概念,其情況就像筆者在點算的奧秘:集合劃分問題中,除了介紹數學界一般界定的「集合劃分問」,即「不容許空集的集合(無序)劃分」問題外,亦提出較廣義的「集合劃分」概念。