整數分拆

维基百科,自由的百科全书
跳转至: 导航搜索

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

  1. a_1 + a_2 + ... + a_k = nk的大小不定)
  2. a_1 \ge a_2 ... \ge a_k
  3. 其他附加條件(例如限定「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)的第幾項(包括p(0))為

1、1、2、3、5、7、11、15、22、30、42、56、77……(OEIS:A000041)

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
***
**
*

***
**
*

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 + 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
  • 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,右邊可寫成:

(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廣義五邊形數

杨氏矩阵的关系[编辑]

一个 (5, 4, 1)分拆表示的杨表

一个杨氏矩阵与一个整数分拆一一对应,也就是说整数分拆的个数等于相应的杨氏矩阵的个数。如图表示一个10=5+4+1的分拆。利用杨氏矩阵来表示的 分拆更具有直观性,和可处理性,下面是几个例子。

分拆的转置[编辑]

(5, 4, 1)分拆的转置(3, 2, 2,2,1)

整数分拆(10=5+4+1)对应的杨氏矩阵沿x=y轴翻转得到新的杨氏矩阵。它对应分拆为10=3+2+2+1。

附加要求的分拆[编辑]

考虑带有附加条件的分拆。

差分拆[编辑]

考虑满足下面条件分拆

  1. a_1 + a_2 + ... + a_k = nk的大小不定)
  2. a_1 > a_2 ... >a_k

及分拆的每个数都不相等。

生成函數

\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(1+x^k\right)

奇分拆[编辑]

考虑满足下面条件分拆

  1. a_1 + a_2 + ... + a_k = nk的大小不定)
  2. a_1 \ge a_2 ... \ge a_k
  3. 要求 a_i(i=1,2,...,k)为奇数

生成函數

\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^{2k-1}} \right).

引理[编辑]

差分拆的个数与奇分拆的个数是一样多的。

可以通过杨表证明。

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. 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。

p_k(n)[编辑]

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

其他常見的問題[编辑]

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

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

外部連結[编辑]