跳转到内容

整数分拆

维基百科,自由的百科全书

一个正整数可以写成一些正整数。在数论上,跟这些和式有关的问题称为整数拆分整数剖分整数分割分割数切割数(英语:Integer partition)。其中最常见的问题就是给定正整数,求不同数组的数目,符合下面的条件:

  1. 的大小不定)
  2. 其他附加条件(例如限定“k是偶数”,或“不是1就是2”等)

分割函数p(n)是求符合以上第一、二个条件的数组数目。

拆分数量数列

4可以用5种方法写成和式:4, 3+1, 2+2, 2+1+1, 1+1+1+1。因此

定义 ,若n为负数则

此函数应用于对称多项式对称群表示理论等。

分割函数p(n),n从0开始:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77......(OEIS:A000041)

程式实现

#include <iostream>
#define MAXLENTH 20000
using namespace std;

int main() {
	const int len = MAXLENTH;
	long num[len + 1] = { 1 }; // 即使使用long也会快速溢出

	for (int i = 1; i <= len; ++i)
		for (int j = i; j <= len; ++j)
			num[j] += num[j - i];

	for (int i = 0; i <= len; i++)
		cout << i << " " << num[i] << endl;
	return 0;
}

Ferrers图示与恒等式

每种分割方法都可用Ferrers图示表示。

Ferrers图示是将第1行放个方格,第2行放个方格……第行放个方格,来表示整数分割的其中一个方法。

借助Ferrers图示,可以推导出许多恒等式

  • 给定正整数k和n,n表达成不多于k个正整数之和的方法数目,等于将n分割成任意个不大于k的正整数之和的方法数目。

证明:将表示前者其中一个数组的Ferrers图示沿对角线反射,便得到后者的一个数组。即两者一一对应,因此其数目相同。

例如 k=3,n=6:

***
*
*
*

****
*
*

6 = 1+1+4 = 1+1+1+3
***
**
*

***
**
*

6 = 1+2+3 = 1+2+3
***
***

**
**
**

6 = 2+2+2 = 3+3

此外,

  • 上述恒等式的值亦等于将表达成刚好个正整数之和的方法的数目。
  • 给定正整数。将表达成两两相异正整数之和的方法的数目,等于将表达成奇数之和的方法的数目。

例如

  1. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
  2. 7 + 1
  3. 3 + 3 + 1 + 1
  4. 5 + 3
  5. 5 + 1 + 1 + 1
  6. 3 + 1 + 1 + 1 + 1 + 1
  1. 8
  2. 7 + 1
  3. 6 + 2
  4. 5 + 3
  5. 5 + 2 + 1
  6. 4 + 3 + 1
  • 表达成个1和个2之和,这些方法的数目是第斐波那契数
  • 表达成多于1的正整数之和的方法数目是p(n) - p(n-1)。

生成函数

生成函数

当|x|<1,右边可写成:

生成函数的倒数为欧拉函数,利用五边形数定理可得到以下的展开式:

生成函数配合五边形数定理,可以得到以下的递归关系式

其中是第广义五边形数

与杨图的关系

一个 (5, 4, 1)分拆表示的杨表

一个杨图唯一地对应于一个整数分拆,也就是说整数分拆的个数等于相应的杨图的个数。如图所示的杨图表示一个10=5+4+1的分拆。利用杨图来表示的分拆更直观性且易操作。

分拆的共轭

(5, 4, 1)分拆的转置(3, 2, 2,2,1)

将整数分拆(10=5+4+1)对应的杨图进行行列反转得到新的杨图(共轭杨图)。它对应的分拆为10=3+2+2+2+1。

Rademacher级数

渐近式:

这式子是1918年哈代拉马努金,以及1920年J. V. Uspensky独立发现的。

1937年,Hans Rademacher得出一个更佳的结果:

其中

表示互质时才计算那项。表示戴德金和。这条公式的证明用上了和戴德金η函数福特圆英语Ford circle法里数列模群英语Modular group

Elder定理

在将表示成正整数之和的所有和式之中,任意正整数作为和项出现在这些式子内的次数,跟每条和式中出现次或以上的正整数数目,相同。

时,此定理又称为Stanley定理。[1][2]

为例:

  • 5
  • 4+1
  • 3+2
  • 3+1+1
  • 2+2+1
  • 2+1+1+1
  • 1+1+1+1+1
  1. 1的总出现次数:0+1+0+2+1+3+5=12;在每条和式出现1次或以上的数的数目:1+2+2+2+2+2+1=12
  2. 2的总出现次数:0+0+1+0+2+1+0=4;在每条和式出现2次或以上的数的数目:0+0+0+1+1+1+1=4。

附加要求的分拆

以下叙述带有附加条件的分拆。

差分拆

考虑满足下面条件分拆

  1. 的大小不定)
  2. 即分拆的每个数都不相等。

生成函数

奇分拆

考虑满足下面条件分拆

  1. 的大小不定)
  2. 要求 为奇数

生成函数

.

引理

差分拆的个数与奇分拆的个数是一样多的。

可以通过杨表证明。

部分个数上限的分拆

当限定将表示成刚好个正整数之和时,可以表示为。显然,

  • 对于
  • (OEIS:A004526)
  • = 最接近的正整数。(OEIS:A069905)

其他常见的问题

不少数学家亦有研究按以下方式分拆的方法数目:

  • 将正整数写成模p同馀r的正整数之和
  • 将模p同馀r正整数写成的正整数之和[3]

参考资料

  1. ^ A Fine Rediscovery (PDF). [2015-11-07]. (原始内容存档 (PDF)于2016-02-22). 
  2. ^ Weisstein, Eric W. (编). Elder's Theorem. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2015-11-07]. (原始内容存档于2020-03-18) (英语). 
  3. ^ Weisstein, Eric W. (编). Partition Function P Congruences. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2006-08-20]. 原始内容存档于2021-02-26 (英语). 

外部链接