一個正整數可以寫成一些正整數的和。在數論上，跟這些和式有關的問題稱為整數拆分、整數剖分、整數分割、分割數或切割數（）。其中最常見的問題就是給定正整數n，求不同數組(a_1,a_2,...,a_k)的數目，符合下面的條件：
a_1 + a_2 + ... + a_k = n （k的大小不定）
a_1 \ge a_2 \ge ... \ge a_k > 0
其他附加條件（例如限定「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......(A000041)
程式實現
#include
#define MAXLENTH 20000
using namespace std;
int main() {
const int len = MAXLENTH;
long num[len + 1] = { 1 }; // 即使使用long也会快速溢出
for (int i = 1; i
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
7 + 1
3 + 3 + 1 + 1
5 + 3
5 + 1 + 1 + 1
3 + 1 + 1 + 1 + 1 + 1
8
7 + 1
6 + 2
5 + 3
5 + 2 + 1
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+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)^ix^{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）对应的杨图进行行列反转得到新的杨图（共轭杨图）。它对应的分拆为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\le m 。
(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的總出現次數：0+1+0+2+1+3+5=12；在每條和式出現1次或以上的數的數目：1+2+2+2+2+2+1=12
2的總出現次數：0+0+1+0+2+1+0=4；在每條和式出現2次或以上的數的數目：0+0+0+1+1+1+1=4。
附加要求的分拆
以下敘述带有附加条件的分拆。
差分拆
考虑满足-{zh-hans:下面条件; zh-hant:下面條件}-分拆
#a_1 + a_2 + \cdots + a_k = n （k的大小不定）
#a_1 > a_2 > \cdots >a_k 即分拆的每个数都不相等。
生成函數是
:\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(1+x^k\right)
奇分拆
考虑满足-{zh-hans:下面条件; zh-hant:下面條件}-分拆
#a_1 + a_2 + \cdots + a_k = n （k的大小不定）
#a_1 \ge a_2 \ge \cdots \ge a_k
要求 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 (A004526)
- p_3(n) = 最接近\frac{n^2}{12}的正整數。(A069905)
- p_{n-1}(n) = 1
- p_k(n) = p_{k-1}(n-1) + p_k(n-k)
其他常見的問題
不少數學家亦有研究按以下方式分拆的方法數目：
- 將正整數寫成模p同餘r的正整數之和
- 將模p同餘r正整數寫成的正整數之和
參考資料
外部連結
- [http://www.math.upenn.edu/%7Ewilf/PIMS/PIMSLectures.pdf Lectures on Integer Partitions] by Herbert S. Wilf
评论 (0)