整數分拆

Template:For Template:Expert 一個正整數可以寫成一些正整數的和。在數論上，跟這些和式有關的問題稱為整數拆分、整數剖分、整數分割、分割數或切割數（Template:Lang-en）。其中最常見的問題就是給定正整數$n$，求不同數組$(a_1,a_2,...,a_k)$的數目，符合下面的條件：

1. $a_1+a_2+...+a_k=n$ （$k$的大小不定）
2. $a_1\ge a_2\ge ...\ge a_k>0$
3. 其他附加條件（例如限定「k是偶數」，或「$a_i$不是1就是2」等）

分割函數p(n)是求符合以上第一、二個條件的數組數目。

拆分數量數列

4可以用5種方法寫成和式：4, 3+1, 2+2, 2+1+1, 1+1+1+1。因此 $p(4)=5$。

定義 $p(0)=1$，若n為負數則 $p(n)=0$。

此函數應用於對稱多項式及對稱群的表示理論等。

分割函數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行放$a_1$個方格，第2行放$a_2$個方格……第$k$行放$a_k$個方格，來表示整數分割的其中一個方法。

借助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

此外，

$6=1+5=1+1+1+1+2$

$6=2+4=2+2+1+1$

$6=3+3=2+2+2$

$6=6=1+1+1+1+1+1$

• 上述恆等式的值亦等於將$n+k$表達成剛好$k$個正整數之和的方法的數目。

• 給定正整數$n$。將$n$表達成兩兩相異正整數之和的方法的數目，等於將$n$表達成奇數之和的方法的數目。

例如$n=8$：

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

• 將$n$表達成$p$個1和$q$個2之和，這些方法的數目是第$n$個斐波那契數。

• 將$n$表達成多於1的正整數之和的方法數目是p(n) - p(n-1)。

生成函數

$p(n)$的生成函數是

$\sum _{n=0}^{\mathrm{\infty }}p(n)x^n=\prod _{k=1}^{\mathrm{\infty }}\left(\frac{1}{1-x^k}\right)$

當|x|<1，右邊可寫成：

$(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+...)...$

$p(n)$生成函數的倒數為歐拉函數，利用五邊形數定理可得到以下的展開式：

$\prod _{k=1}^{\mathrm{\infty }}(1-x^k)=\sum _{i=-\mathrm{\infty }}^{\mathrm{\infty }}(-1{)}^i{x}^{i(3i-1)/2}.$

將$p(n)$生成函數配合五邊形數定理，可以得到以下的遞歸關係式

$p(n)=\sum _i(-1{)}^{i-1}p(n-q_i)$

其中$q_i$是第$i$個廣義五邊形數。

与杨图的关系

一个 (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級數

漸近式：

$p(n)\sim \frac{\exp \left(\pi \sqrt{2n/3}\right)}{4n\sqrt{3}}\text{ as }n\to \mathrm{\infty }.$

這式子是1918年哈代和拉馬努金，以及1920年J. V. Uspensky獨立發現的。

1937年，Hans Rademacher得出一個更佳的結果：

$p(n)=\frac{1}{\pi \sqrt{2}}\sum _{k=1}^{\mathrm{\infty }}{A}_k(n)\sqrt{k}\frac{d}{dn}\left(\frac{\sinh \left(\frac{\pi }{k}\sqrt{\frac{2}{3}(n-\frac{1}{24})}\right)}{\sqrt{n-\frac{1}{24}}}\right)$

其中

$A_k(n)=\sum _{0\le m<k;(m,k)=1}\exp (\pi is(m,k)-2\pi inm/k).$。

$(m,n)=1$表示$m,n$互質時才計算那項。$s(m,k)$表示戴德金和。這條公式的證明用上了和戴德金η函數、Template:Link-en、法里數列、Template:Link-en。

Elder定理

在將$n$表示成正整數之和的所有和式之中，任意正整數$r$作為和項出現在這些式子內的次數，跟每條和式中出現$r$次或以上的正整數數目，相同。

當$r=1$時，此定理又稱為Stanley定理。

以$n=5$為例：

• 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。

附加要求的分拆

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

差分拆

考虑满足-{zh-hans:下面条件; zh-hant:下面條件}-分拆

1. $a_1+a_2+\cdots +a_k=n$ （$k$的大小不定）
2. $a_1>a_2>\cdots >a_k$ 即分拆的每个数都不相等。

生成函數是

$\sum _{n=0}^{\mathrm{\infty }}p(n)x^n=\prod _{k=1}^{\mathrm{\infty }}(1+x^k)$

奇分拆

考虑满足-{zh-hans:下面条件; zh-hant:下面條件}-分拆

1. $a_1+a_2+\cdots +a_k=n$ （$k$的大小不定）
2. $a_1\ge a_2\ge \cdots \ge a_k$
3. 要求 $a_i(i=1,2,\dots ,k)$为奇数

生成函數是

$\sum _{n=0}^{\mathrm{\infty }}p(n)x^n=\prod _{k=1}^{\mathrm{\infty }}\left(\frac{1}{1-x^{2k-1}}\right)$.

引理

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

可以通过杨表证明。

部分個數上限的分拆

當限定將$n$表示成剛好$k$個正整數之和時，可以表示為$p_k(n)$。顯然，$p(n)=\sum _{k=1}^n{p}_k(n)$。

• 對於$n>1$，$p_n(n)=p_1(n)=1$
• $p_2(n)=\lfloor \frac{n}{2}\rfloor$ (OEIS:A004526)
• $p_3(n)$ = 最接近$\frac{n^2}{12}$的正整數。(OEIS:A069905)
• $p_{n-1}(n)=1$
• $p_k(n)=p_{k-1}(n-1)+p_k(n-k)$

其他常見的問題

不少數學家亦有研究按以下方式分拆的方法數目：

• 將正整數寫成模p同餘r的正整數之和
• 將模p同餘r正整數寫成的正整數之和

外部連結

• Lectures on Integer Partitions Template:Wayback by Herbert S. Wilf