整數分拆
维基百科,自由的百科全书
一個正整數可以寫成一些正整數的和。在數論上,跟這些和式有關的問題稱為整數分拆、整數剖分或整數分割。其中最常見的問題就是給定正整數n,求不同數組(a1,a2,...,ak)的數目,符合下面的條件:
- a1 + a2 + ... + ak = n (k的大小不定)
- 其他附加條件(例如限定「k是偶數」,或「ai不是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。
[编辑] Ferrers圖示與恆等式
每種分割方法都可用Ferrers圖示表示。
Ferrers圖示是將第1行放a1個方格,第2行放a2個方格……第k行放ak個方格,來表示整數分割的其中一個方法。
借助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
- 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) = | ∑ | ( − 1)i − 1p(n − qi) |
i |
,其中qi是第i個五邊形數。說明可見於五邊形數定理。
[编辑] 生成函數
p(n)的生成函數是
當|x|<1,右邊可寫成:
- (1 + x + x2 + x3 + ...)(1 + x2 + x4 + x6 + ...)(1 + x3 + x6 + ...)...
[编辑] Rademacher級數
漸近式:
這式子是1918年哈代和拉馬努金,以及1920年J. V. Uspensky獨立發現的。
1937年,Hans Rademacher得出一個更佳的結果:
其中
- 。
(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。
[编辑] pk(n)
當限定將n表示成剛好k個正整數之和時,可以表示為pk(n)。顯然,。
- 對於n > 1,pn(n) = p1(n) = p2(n) = = 1
- (OEIS:A004526)
- p3(n) = 最接近的正整數。(OEIS:A069905)
- pn − 1(n) = C(n,2)
- pk(n) = pk − 1(n − 1) + pk(n − k)
[编辑] 其他常見的問題
不少數學家亦有研究按以下方式分拆的方法數目:
- 將正整數寫成模p同餘r的正整數之和
- 將模p同餘r正整數寫成的正整數之和[1]
[编辑] 外部連結
- Lectures on Integer Partitions by Herbert S. Wilf