关于將整數寫成其他整數的乘積,请见「
整数分解」。
| 此條目需要 精通或熟悉相关主题的编者参与及协助编辑。 (2013年12月31日) 請邀請適合的人士改善本条目。更多的細節與詳情請參见討論頁。 |
一個正整數可以寫成一些正整數的和。在數論上,跟這些和式有關的問題稱為整數拆分、整數剖分、整數分割、分割數或切割數(英語:Integer partition)。其中最常見的問題就是給定正整數,求不同數組的數目,符合下面的條件:
- (的大小不定)
- 其他附加條件(例如限定「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:
此外,
- 上述恆等式的值亦等於將表達成剛好個正整數之和的方法的數目。
- 給定正整數。將表達成兩兩相異正整數之和的方法的數目,等於將表達成奇數之和的方法的數目。
例如:
- 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
- 將表達成個1和個2之和,這些方法的數目是第個斐波那契數。
- 將表達成多於1的正整數之和的方法數目是p(n) - p(n-1)。
生成函數
的生成函數是
當|x|<1,右邊可寫成:
生成函數的倒數為歐拉函數,利用五邊形數定理可得到以下的展開式:
將生成函數配合五邊形數定理,可以得到以下的遞歸關係式
其中是第個廣義五邊形數。
与杨图的关系
一个杨图唯一地对应于一个整数分拆,也就是说整数分拆的个数等于相应的杨图的个数。如图所示的杨图表示一个10=5+4+1的分拆。利用杨图来表示的分拆更直观性且易操作。
分拆的共轭
将整数分拆(10=5+4+1)对应的杨图进行行列反转得到新的杨图(共轭杨图)。它对应的分拆为10=3+2+2+2+1。
Rademacher級數
漸近式:
這式子是1918年哈代和拉馬努金,以及1920年J. V. Uspensky獨立發現的。
1937年,Hans Rademacher得出一個更佳的結果:
其中
- 。
表示互質時才計算那項。表示戴德金和。這條公式的證明用上了和戴德金η函數、福特圓、法里數列、模群。
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的總出現次數: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。
附加要求的分拆
以下敘述带有附加条件的分拆。
差分拆
考虑满足下面条件分拆
- (的大小不定)
- 即分拆的每个数都不相等。
生成函數是
奇分拆
考虑满足下面条件分拆
- (的大小不定)
- 要求 为奇数
生成函數是
- .
引理
差分拆的个数与奇分拆的个数是一样多的。
可以通过杨表证明。
部分個數上限的分拆
當限定將表示成剛好個正整數之和時,可以表示為。顯然,。
- 對於,
- (OEIS:A004526)
- = 最接近的正整數。(OEIS:A069905)
其他常見的問題
不少數學家亦有研究按以下方式分拆的方法數目:
- 將正整數寫成模p同餘r的正整數之和
- 將模p同餘r正整數寫成的正整數之和[3]
參考資料
外部連結