整数的分拆

一个正整数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)表出。由此可见，组合数学是个无底洞，能够有个显示表达式的量太少了。