整數的分拆

一個正整數n的分拆，是指把它寫成一些正整數之和，要求算出分拆方式的總數。有多種不同的分拆方式。如果考慮順序的話，可以想像把n個1排成一行，有n – 1個空檔；每個空檔可以用或不用豎杆把它們分隔開，分拆總數為 2^(n-1)。也可以按照加項個數求出，分成1，2，3， 。。。，n個加項，總數為1 + C(n-1, 1) + C(n-1, 2) + … + C(n-1, n- 1)。

不計順序時，我們用p(n)表示分拆總數。規定p(0) = 1, p(1) = 1；容易算出p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7等。一般計算方式是用生成函數：G(x) = sigma{p(n)x^n: n = 0, 1, 2, ….}；用另一種方式來計算可得，G(x) = sum{x^(1n1+…+knk): nj ≥ 0, k ≥ 1} , 其中，在n的分拆中，n1表示1的個數，。。。nk表示k的個數。因此，

G(x) = Product{sum[x^(jnj): nj = 0, 1, 2, ….], j = 1, 2, 3, …} = Product {(1 – x^j)^(-1): j = 1, 2, 3, …}.

G(x)的倒數等於Product {(1 – x^j): j = 1, 2, 3, …} = 1 – x – x^2 + x^5 + x^7 – x^12 – x^15 + …

指數的一般公式為 (3i^2 – i)/2,（3i^2 + i）/2，冪前麵帶符號(-1)^(i+1)。歐拉推出了一個遞推公式：

p(n) = Σ(-1)^i+lp(n – (3i² + i)/2) + Σ(-1)ⁱ⁺¹p(n – (3i² - i)/2), 亦即

p(n) = p(n – 1) + p(n – 2) – p(n – 5) – p(n – 7) + p(n – 12) + p(n – 15) –... .

對G(x)取對數再對x求導數，可得xG’(x)/G(x) = Sum{jx^(j)/(1 – x^j): j = 1, 2, 3, ….}；這種級數被稱為Lambert級數。把它展開成冪級數，可得：sum{jx^jk: j,k = 1, 2, 3, …} = sum{d(m)x^m: m = 1, 2, 3, … }，其中d(m)為m的整數因子之和。由此，可以推出d(m)的遞推公式：

d(m) = d(m-1) + d(m – 2) – d(m – 5) – d(m-7) + d(m-12) + d(m-15) - …

還可以把n分拆為奇數之和，其生成函數為 O(x) = (1 – x)^-1 (1 – x³)^-1(1 – x⁵)^-1... ; 也可以把n分拆為不相等的整數之和，生成函數是 U(x) = (1 + x)(1 + x²)(1+ x³)... 如果把n分拆為連續正整數之和，則分拆總數等於n的奇因數的個數；這可以從簡單的算術級數，通過解二次不定方程得出。

自然還有正整數的積性分拆，即是把n寫成大於·1的正整數的乘積，不計順序；設分拆方法的總數為q(n)，並規定q(1) = 1。這是Euclid競賽2013年的最後一道題，它隻給出了部分解答。顯然，當n = p^m，p為質數，m為正整數時，q(n) = p(m)。如果n是兩個不同質數冪的乘積，如n = (p1)^m1 * (p2)^m2，q(n)的值顯然與p1,p2的具體值無關，分拆總數可計為Q(m1,m2) (m1,m2的位置可以互換)。

Q(1, m)可以分兩種情況計算：一是把p1單列為一個因子，共有p(m)種分拆方式；二是把p1並入到(p2)^m的某個分拆中，即寫成(p1)(p2)^k * (p2)^(m-k)；0 < k < m；分拆總數是sum{p(m-k) : k = 1, 2, …, m-1}。故Q(1, m) = sum{P(k): k = 1, 2, …, m}。

對於Q(2, m)，可分三種情況：（1）(p1)^2為單獨一個因子，有P(m)種方式；（2）(p1)^2並入到p2的某個冪中：[（p1）^2 (p2)^k]* (p2)^(m-k)，計有sum{P(m-k): k = 1, …, m-1} 種方式。（3）[p1*(p2)^k] [p1*(p2)^j] (p2)^(m -k-j)，計有sum{P(m – k – j): 0<k ≤j，k + j ≤m}種方式。故Q(2,m) =sum{P(m-k): k =0, 1, …,m-1} + sum{P(m-h)*fl(h/2): h=2, …, m}，其中，fl(h/2)是h/2向下取整。

對於一般的Q(j, m)，可設j≤m。可以設想(p1)^n * (p2)^m = (p1p2^k1)…(p1p2^kj) * (p2)^(m – k1 – k2 .. – kj)，由於不計順序，可設0 ≤k1≤…≤kj, k1 + k2 + … + kj ≤ m。Q(n, m)即是所有P(m-k1-k2-…-kj)之和，ki滿足上述條件。

當n為更多個不同質數冪的乘積時，表達式就更複雜了，盡管還可以用函數P(k)表出。由此可見，組合數學是個無底洞，能夠有個顯示表達式的量太少了。