整數分拆

關於將整數寫成其他整數的乘積，請見「整數分解」。

一個正整數可以寫成一些正整數的和。在數論上，跟這些和式有關的問題稱為整數拆分、整數剖分、整數分割、分割數或切割數（英語：Integer partition）。其中最常見的問題就是給定正整數${\displaystyle n}$，求不同數組${\displaystyle (a_{1},a_{2},...,a_{k})}$的數目，符合下面的條件：

1. ${\displaystyle a_{1}+a_{2}+...+a_{k}=n}$ （${\displaystyle k}$的大小不定）
2. ${\displaystyle a_{1}\geq a_{2}\geq ...\geq a_{k}>0}$
3. 其他附加條件（例如限定「k是偶數」，或「${\displaystyle a_{i}}$不是1就是2」等）

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

拆分數量數列

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

定義 ${\displaystyle p(0)=1}$，若n為負數則 ${\displaystyle 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行放${\displaystyle a_{1}}$個方格，第2行放${\displaystyle a_{2}}$個方格……第${\displaystyle k}$行放${\displaystyle 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

此外，

${\displaystyle 6=1+5=1+1+1+1+2}$

${\displaystyle 6=2+4=2+2+1+1}$

${\displaystyle 6=3+3=2+2+2}$

${\displaystyle 6=6=1+1+1+1+1+1}$

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

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

例如${\displaystyle 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

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

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

生成函數

${\displaystyle p(n)}$的生成函數是

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

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

${\displaystyle (1+x+x^{2}+x^{3}+...)(1+x^{2}+x^{4}+x^{6}+...)(1+x^{3}+x^{6}+...)...}$

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

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

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

${\displaystyle p(n)=\sum _{i}(-1)^{i-1}p(n-q_{i})}$

其中${\displaystyle q_{i}}$是第${\displaystyle 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級數

漸近式：

${\displaystyle p(n)\sim {\frac {\exp \left(\pi {\sqrt {2n/3}}\right)}{4n{\sqrt {3}}}}{\mbox{ as }}n\rightarrow \infty .}$

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

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

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

其中

${\displaystyle A_{k}(n)=\sum _{0\leq m<k\;;\;(m,k)=1}\exp \left(\pi is(m,k)-2\pi inm/k\right).}$。

${\displaystyle (m,n)=1}$表示${\displaystyle m,n}$互質時才計算那項。${\displaystyle s(m,k)}$表示戴德金和。這條公式的證明用上了和戴德金η函數、福特圓（英語：Ford circle）、法里數列、模群（英語：Modular group）。

Elder定理

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

當${\displaystyle r=1}$時，此定理又稱為Stanley定理。^[1][2]

以${\displaystyle 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。

附加要求的分拆

以下敘述帶有附加條件的分拆。

差分拆

考慮滿足下面條件分拆

1. ${\displaystyle a_{1}+a_{2}+\cdots +a_{k}=n}$ （${\displaystyle k}$的大小不定）
2. ${\displaystyle a_{1}>a_{2}>\cdots >a_{k}}$ 即分拆的每個數都不相等。

生成函數是

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

奇分拆

考慮滿足下面條件分拆

1. ${\displaystyle a_{1}+a_{2}+\cdots +a_{k}=n}$ （${\displaystyle k}$的大小不定）
2. ${\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{k}}$
3. 要求 ${\displaystyle a_{i}(i=1,2,\ldots ,k)}$為奇數

生成函數是

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

引理

差分拆的個數與奇分拆的個數是一樣多的。

可以通過楊表證明。

部分個數上限的分拆

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

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

其他常見的問題

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

• 將正整數寫成模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 （英語）.

外部連結

• Lectures on Integer Partitions （頁面存檔備份，存於互聯網檔案館） by Herbert S. Wilf