整數分割

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

 1. $a_{1}+a_{2}+...+a_{k}=n$ （ $k$ 的大小不定）
2. $a_{1}\geq a_{2}\geq ...\geq 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)

### 程式實現

## 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+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}^{\infty }p(n)x^{n}=\prod _{k=1}^{\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}^{\infty }(1-x^{k})=\sum _{i=-\infty }^{\infty }(-1)^{i}x^{i(3i-1)/2}.$

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

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

其中 $q_{i}$ 是第 $i$ 個廣義五邊形數。

## 與楊氏矩陣的關係

一個楊氏矩陣與一個整數分拆一一對應，也就是說整數分拆的個數等於相應的楊氏矩陣的個數。如圖表示一個 10=5+4+1 的分拆。利用楊氏矩陣來表示的
分拆更具有直觀性，和可處理性，下面是幾個例子。

### 分拆的轉置

整數分拆（10=5+4+1）對應的楊氏矩陣沿 x=y 軸翻轉得到新的楊氏矩陣。它對應分拆為 10=3+2+2+2+1。

　
:

## Rademacher 級數

漸近式：

　
: $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 得出一個更佳的結果：

　
: $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)$

其中

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

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

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

## 附加要求的分拆

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

### 差分拆

考慮滿足下面條件分拆

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

生成函數是

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

### 奇分拆

考慮滿足下面條件分拆

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

生成函數是

　
: $\sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\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)=\left\lfloor {\frac {n}{2}}\right\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 （頁面存檔備份，存於網際網路檔案館） by Herbert S. Wilf