點算的奧秘:整數分割問題


筆者在《點算的奧秘:分配問題》中介紹了兩種「整數分割」 問題:「整數有序分割」問題和「整數(無序)分割」問題。它們分別對應著兩種「分配」 問題和「組合」問題(參見上述網頁的表2)。由於「整數有序分割」問題對應著我們熟知的「組合」問題,「組 合」問題的所有定理、公式、解題技巧都可應用於「整數有序分割」問題,本網頁不考慮這種「整數分割」問 題,因此如無特別註明,本網頁討論的「整數分割」問題都是指「整數(無序)分割」問題。

「整數分割」問題是指以下問題:現要把正整數r分割為若干個(沒有固定次序的)非負整數(稱為「部分」Part) 相加之和,問有多少種不同分割法?由於各部分無次序之分,以下我們規定在列出某個正整數的各部分時,把 它們按遞增序排列。正如以前介紹的各類「點算組合學」問題一樣,「整數分割」問題可以按照添加於其上的 各種限制條件而分為多種類別。這些限制條件可分為兩大類:

(1)對各部分大小的限制條件(例如規定各部分的上、下限)
(2)對部分個數的限制條件(例如規定把r分割為n個部分)

特別地,在「點算組合學」上一般規定各部分的下限為1 (註1)。因此在以下討論中,如無特別註明,我們的「 整數分割」問題都是各部分下限為1的「整數分割」問題,即我們只考慮把r分割為若干個整數相加之 和的問題。在「點算組合學」上,一般把r的「分割」方案總數記為p(r)。

筆者在《點算的奧秘:分配問題》中曾指出,我們不能單靠以往介紹的方 法(例如「容斥原理」),而必須運用新的方法來解決「整數分割」問題,前數節介紹的「母函數」方法就是這 種新方法。事實上,我們無法用一條公式來表達p(r)的值。為方便以後的討論,現首先把p(r)的部分數值列於 下表:

表1
r12345678 910
p(r)12357111522 3042

以下我們用「母函數」方法求p(r),即求解最簡單的,不含任何限制條件的「整數分割」問題。我們可以把這 種「整數分割」問題轉化為一種我們以前處理過的問題。我們用k1、k2 ... kr分別代表在r的某一「分割」方案中所出現的1、2 ... r的個數。請注意下式是成立的:

k1 + 2k2 + 3k3 + ... rkr = r     (1)

舉例說,我們可以把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)修改為下式:

k1 + 2k2 + + ... iki + ...    (2)

這裡既不事先規定上式包含多少個項,也不事先規定這些項相加後等於甚麼值,是因為我們希望「母函數」不 僅可解決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)的母函數」

(1 + x + x2 + ...) × (1 + x2 + x4 + ...) × ... (1 + xi + x2i + ...) × ...    (3)

p(r) (即r的「分割」方案總數)就是上式展開式中xr項的「系數」。有些人可能覺得奇怪,上式是 一個「無窮乘積」,如何能把它展開?答案是我們不必真的把上式展開。由於在實際問題中,被分割的r總是一 個有限數,在尋求xr項的「系數」時,我們實際只需考慮前r個「括弧」的乘積,而且在每個「括 弧」中,只需考慮有限個項,凡是形如xs (s > r)的項都不用考慮,因為這些項與其他項相乘,不 可能得出xr。以下例題顯示如何利用上方法求p(r)。

例題1:試求5的「分割」方案總數,即p(5)。

答1:本題的「母函數」為:

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

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)改寫成

(1 − x)−1 × (1 − x2)−1 × ... (1 − xi)−1 × ... = Π1 ≤ i < ∞ (1 − xi)−1 (註2)    (4)

但由於各個「括弧」的內容不同,上式難以再作化簡,因此上式只有理論意義,並不方便計算。在實際計算 p(r)時,我們還是要使用公式(3)的形式。在沒有電腦軟件的情況下,利用公式(3)求p(r)其實跟憑個人智慧找 出p(r)沒有太大差別。不過正如筆者多次強調的,「母函數」為我們提供了表達某些點算問題的簡單而有系統 的方法,因而是有價值的。而且「母函數」方法不僅可用來解決「點算型整數分割」問題,還能解決 「列舉型整數分割」問題,其方法跟《點算的奧秘:列舉型母函數》 中介紹的方法完全相同。假如我們用符號N1、N2 ...分別代表整數1、2 ...,並 把這些符號加入上面的公式(3),便得到以下的「求p(r)的列舉型母函數」

[1 + N1x + (N1x)2 + ...] × [1 + N2x2 + (N2x2)2 + ...] × ... [1 + Nixi + (Nixi)2 + ...] × ...    (5)

例題2:列出5的所有「分割」方案。

答2:本題是例題1的延續,因此只需把該題的「母函數」修改為下式,便可用來解答本題:

[1 + N1x + (N1x)2 + (N1x)3 + (N1x)4 + (N1x)5 + ...] × [1 + N2x2 + (N2x2)2 + ...]
× [1 + N3x3 + ...] × [1 + N4x4 + ...] × [1 + N5x5 + ...] × ...

本題答案就是上式展開式中x5項的「系數」。根據例題1的解答,容易得到這個「系數」為

N5 + N2N3 + N1N4 + N1N22 + N12N3 + N13N2 + N15

上式的各項代表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的「括弧」中。因此本題的「列舉型母函數」為

[N2x2 + (N2x2)2 + (N2x2)3] × [1 + N4x4 + (N4x4)2 + ...] × [1 + N6x6 + ...] × [1 + N8x8 + ...] × ...

本題答案就是上式展開式中x10項的「系數」。根據觀察,這個「系數」是

N2N8 + N2N42 + N22N6 + N23N4

上式的各項代表符合給定條件的4個「分割」方案。例如N23N4便代表 2+2+2+4。□

例題4:現要把9分割為各不相等的部分。試列出所有「分割」方案。

答4:初看起來,本題的限制條件似乎跟前面介紹的很不相同,難以用「母函數」來表達,但其實也 可以看成帶某種「上限」。規定各部分不相等,其實就等於規定在「分割」方案中,每個整數最多只能出現1次 ,即各個部分的「上限」為1。這樣我們便可以用前面的方法把本題的限制條件表達為「母函數」了。

由於各個部分的「上限」為1,本題的「列舉型母函數」為

(1 + N1x) × (1 + N2x2) × (1 + N3x3) × (1 + N4x4) × (1 + N5x5) × (1 + N6x6) × (1 + N7x7) × (1 + N8x8) × (1 + N9x9) × ...

本題答案就是上式展開式中x9項的「系數」。根據觀察,這個「系數」是

N9 + N4N5 + N3N6 + N2N7 + N2N3N4 + N1N8 + N1N3N5 + N1N2N6

上式的各項代表符合給定條件的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)求解。

|S1' ∩ S2' ∩ S3'| = |U| + Σ1 ≤ k ≤ 3(−1)k S3, k     (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)求得本題答案為

|U| − S3, 1 + S3, 2 − S3, 3 = 15 − 8 + 0 − 0 = 7 □

請注意,我們也可用「母函數」方法解上題,但似乎不及「容斥原理」那麼簡潔。由此可見,「點算組合學」 問題並無放諸四海而皆準的解題方法,我們必須靈活運用各種技巧。

註1:數學界在提到「整數分割」問題時,一般都是本網頁所指的那種「狹義」的「整數分割」問題,即各部分 下限為1的「整數(無序)分割」問題,他們一般不考慮「整數有序分割」問題或容許下限為0的「整數分割」問 題。本網站只是純粹出於概念完整性和對稱性的考慮,才提出較廣義的「整數分割」概念,其情況就像筆者在 點算的奧秘:集合劃分問題中,除了介紹數學界一般界定的「集合劃分問 」,即「不容許空集的集合(無序)劃分」問題外,亦提出較廣義的「集合劃分」概念。

註2:本公式中的符號Π代表「連乘積」,其作用和結構類似「求和符號」Σ,也有「連乘積變項」(即 本公式中的i)和上、下限。



返回數學專題
<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>