数论人生

数论是一门学科,也是我的人生。有人把酒论英雄,我用数字描天下。
个人资料
欧洲联盟 (热门博主)
  • 博客访问:
正文

整数的分拆

(2022-03-11 11:46:52) 下一个

一个正整数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 – (3i2 + i)/2) + Σ(-1)i+1p(n – (3i2 - 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 – x3)-1(1 – x5)-1... ; 也可以把n分拆为不相等的整数之和,生成函数是 U(x) = (1 + x)(1 + x2)(1+ x3)... 如果把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)表出。由此可见,组合数学是个无底洞,能够有个显示表达式的量太少了。

[ 打印 ]
阅读 ()评论 (0)
评论
目前还没有任何评论
登录后才可评论.