整數分拆

维库，知识与思想的自由文库

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

$a 1 + a 2 + ... + a k = n$ （ $k$ 的大小不定）
$a_1 \ge a_2 ... \ge a_k$
其他附加條件（例如限定「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。

這個函數應用於對稱多項式、對稱群和表示理論等。

[编辑] 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+1+4=1+1+1+3
 xxxx   xxx
 x      x
 x      x
        x

 6=1+2+3=1+2+3
 xxx  xxx
 xx   xx
 x    x

 6=2+2+2=3+3
 xx  xxx
 xx  xxx
 xx

 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) = s u m i ( - 1) i - 1 p (n - q i)$ ，其中 $q i$ 是第 $i$ 個五邊形數。說明可見於五邊形數定理。

[编辑] 生成函數

$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 + ...)...

[编辑] 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 < k \; ; \; (m,k)=1}\exp \left( \pi i s(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的總出現次數：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。

[编辑] p_k(n)

當限定將 $n$ 表示成剛好 $k$ 個正整數之和時，可以表示為 $p k (n)$ 。顯然， $p(n) = \sum_{k=1}^{n} p_k(n)$ 。

對於 $n > 1$ ， $p n (n) = p 1 (n) = p 2 (n) = = 1$
$p_2(n) = \lfloor \frac{n}{2} \rfloor$ (OEIS:A004526)
$p 3 (n)$ = 最接近 $\frac{n^2}{12}$ 的正整數。(OEIS:A069905)
$p n - 1 (n) = C (n,2)$
$p k (n) = p k - 1 (n - 1) + p k (n - k)$

[编辑] 其他常見的問題

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

將正整數寫成模p同餘r的正整數之和
將模p同餘r正整數寫成的正整數之和[1]

[编辑] 外部連結

Lectures on Integer Partitions by Herbert S. Wilf

来自“http://www.chinawiki.org/wiki/%E6%95%B4%E6%95%B8%E5%88%86%E6%8B%86”

个人工具