跳至內容

整數分拆

維基百科,自由的百科全書

一個正整數可以寫成一些正整數。在數論上,跟這些和式有關的問題稱為整數拆分整數剖分整數分割分割數切割數(英語:Integer partition)。其中最常見的問題就是給定正整數,求不同數組的數目,符合下面的條件:

  1. 的大小不定)
  2. 其他附加條件(例如限定「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:

***
*
*
*

****
*
*

6 = 1+1+4 = 1+1+1+3
***
**
*

***
**
*

6 = 1+2+3 = 1+2+3
***
***

**
**
**

6 = 2+2+2 = 3+3

此外,

  • 上述恆等式的值亦等於將表達成剛好個正整數之和的方法的數目。
  • 給定正整數。將表達成兩兩相異正整數之和的方法的數目,等於將表達成奇數之和的方法的數目。

例如

  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
  • 表達成個1和個2之和,這些方法的數目是第斐波那契數
  • 表達成多於1的正整數之和的方法數目是p(n) - p(n-1)。

生成函數

[編輯]

生成函數

當|x|<1,右邊可寫成:

生成函數的倒數為歐拉函數,利用五邊形數定理可得到以下的展開式:

生成函數配合五邊形數定理,可以得到以下的遞歸關係式

其中是第廣義五邊形數

與楊圖的關係

[編輯]
一個 (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級數

[編輯]

漸近式:

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

1937年,Hans Rademacher得出一個更佳的結果:

其中

表示互質時才計算那項。表示戴德金和。這條公式的證明用上了和戴德金η函數福特圓英語Ford circle法里數列模群英語Modular group

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. 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. 的大小不定)
  2. 即分拆的每個數都不相等。

生成函數

奇分拆

[編輯]

考慮滿足下面條件分拆

  1. 的大小不定)
  2. 要求 為奇數

生成函數

.

引理

[編輯]

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

可以通過楊表證明。

部分個數上限的分拆

[編輯]

當限定將表示成剛好個正整數之和時,可以表示為。顯然,

  • 對於
  • (OEIS:A004526)
  • = 最接近的正整數。(OEIS:A069905)

其他常見的問題

[編輯]

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

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

外部連結

[編輯]