此條目需要精通或熟悉相关主题的编者参与及协助编辑。 (2013年12月31日)請
邀請 適合的人士
改善本条目 。更多的細節與詳情請參见
討論頁 。
一個正整數 可以寫成一些正整數 的和 。在數論 上,跟這些和式有關的問題稱為整數拆分 、整數剖分 、整數分割 、分割數 或切割數 (英語:Integer partition )。其中最常見的問題就是給定正整數
n
{\displaystyle n}
,求不同數組
(
a
1
,
a
2
,
.
.
.
,
a
k
)
{\displaystyle (a_{1},a_{2},...,a_{k})}
的數目,符合下面的條件:
a
1
+
a
2
+
.
.
.
+
a
k
=
n
{\displaystyle a_{1}+a_{2}+...+a_{k}=n}
(
k
{\displaystyle k}
的大小不定)
a
1
≥
a
2
≥
.
.
.
≥
a
k
>
0
{\displaystyle a_{1}\geq a_{2}\geq ...\geq a_{k}>0}
其他附加條件(例如限定「k是偶數」,或「
a
i
{\displaystyle a_{i))
不是1就是2」等) 分割函數 p(n )是求符合以上第一、二個條件的數組數目。
4可以用5種方法寫成和式:4, 3+1, 2+2, 2+1+1, 1+1+1+1。因此
p
(
4
)
=
5
{\displaystyle p(4)=5}
。
定義
p
(
0
)
=
1
{\displaystyle p(0)=1}
,若n為負數則
p
(
n
)
=
0
{\displaystyle p(n)=0}
。
此函數應用於對稱多項式 及對稱群 的表示理論 等。
分割函數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圖示是將第1行放
a
1
{\displaystyle a_{1))
個方格,第2行放
a
2
{\displaystyle a_{2))
個方格……第
k
{\displaystyle k}
行放
a
k
{\displaystyle a_{k))
個方格,來表示整數分割的其中一個方法。
借助Ferrers圖示,可以推導出許多恆等式 :
給定正整數k和n,n表達成不多於k個正整數之和的方法數目,等於將n分割成任意個不大於k的正整數之和的方法數目。 證明:將表示前者其中一個數組的Ferrers圖示沿對角線反射,便得到後者的一個數組。即兩者一一對應,因此其數目相同。
例如 k=3,n=6:
此外,
6
=
1
+
5
=
1
+
1
+
1
+
1
+
2
{\displaystyle 6=1+5=1+1+1+1+2}
6
=
2
+
4
=
2
+
2
+
1
+
1
{\displaystyle 6=2+4=2+2+1+1}
6
=
3
+
3
=
2
+
2
+
2
{\displaystyle 6=3+3=2+2+2}
6
=
6
=
1
+
1
+
1
+
1
+
1
+
1
{\displaystyle 6=6=1+1+1+1+1+1}
上述恆等式的值亦等於將
n
+
k
{\displaystyle n+k}
表達成剛好
k
{\displaystyle k}
個正整數之和的方法的數目。 給定正整數
n
{\displaystyle n}
。將
n
{\displaystyle n}
表達成兩兩相異正整數之和的方法的數目,等於將
n
{\displaystyle n}
表達成奇數 之和的方法的數目。 例如
n
=
8
{\displaystyle 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
{\displaystyle n}
表達成
p
{\displaystyle p}
個1和
q
{\displaystyle q}
個2之和,這些方法的數目是第
n
{\displaystyle n}
個斐波那契數 。 將
n
{\displaystyle n}
表達成多於1的正整數之和的方法數目是p(n ) - p(n -1)。
p
(
n
)
{\displaystyle p(n)}
的生成函數 是
∑
n
=
0
∞
p
(
n
)
x
n
=
∏
k
=
1
∞
(
1
1
−
x
k
)
{\displaystyle \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
+
.
.
.
)
.
.
.
{\displaystyle (1+x+x^{2}+x^{3}+...)(1+x^{2}+x^{4}+x^{6}+...)(1+x^{3}+x^{6}+...)...}
p
(
n
)
{\displaystyle p(n)}
生成函數的倒數為歐拉函數 ,利用五邊形數定理 可得到以下的展開式:
∏
k
=
1
∞
(
1
−
x
k
)
=
∑
i
=
−
∞
∞
(
−
1
)
i
x
i
(
3
i
−
1
)
/
2
.
{\displaystyle \prod _{k=1}^{\infty }(1-x^{k})=\sum _{i=-\infty }^{\infty }(-1)^{i}x^{i(3i-1)/2}.}
將
p
(
n
)
{\displaystyle p(n)}
生成函數配合五邊形數定理 ,可以得到以下的遞歸關係式
p
(
n
)
=
∑
i
(
−
1
)
i
−
1
p
(
n
−
q
i
)
{\displaystyle p(n)=\sum _{i}(-1)^{i-1}p(n-q_{i})}
其中
q
i
{\displaystyle q_{i))
是第
i
{\displaystyle i}
個廣義五邊形數 。
一个 (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。
漸近式:
p
(
n
)
∼
exp
(
π
2
n
/
3
)
4
n
3
as
n
→
∞
.
{\displaystyle 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
)
=
1
π
2
∑
k
=
1
∞
A
k
(
n
)
k
d
d
n
(
sinh
(
π
k
2
3
(
n
−
1
24
)
)
n
−
1
24
)
{\displaystyle 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
)
=
∑
0
≤
m
<
k
;
(
m
,
k
)
=
1
exp
(
π
i
s
(
m
,
k
)
−
2
π
i
n
m
/
k
)
.
{\displaystyle A_{k}(n)=\sum _{0\leq m<k\;;\;(m,k)=1}\exp \left(\pi is(m,k)-2\pi inm/k\right).}
。
(
m
,
n
)
=
1
{\displaystyle (m,n)=1}
表示
m
,
n
{\displaystyle m,n}
互質時才計算那項。
s
(
m
,
k
)
{\displaystyle s(m,k)}
表示戴德金和 。這條公式的證明用上了和戴德金η函數 、福特圓 、法里數列 、模群 。
在將
n
{\displaystyle n}
表示成正整數之和的所有和式之中,任意正整數
r
{\displaystyle r}
作為和項出現在這些式子內的次數,跟每條和式中出現
r
{\displaystyle r}
次或以上的正整數數目,相同。
當
r
=
1
{\displaystyle r=1}
時,此定理又稱為Stanley定理。[ 1] [ 2]
以
n
=
5
{\displaystyle 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。 以下敘述带有附加条件的分拆。
考虑满足下面条件分拆
a
1
+
a
2
+
⋯
+
a
k
=
n
{\displaystyle a_{1}+a_{2}+\cdots +a_{k}=n}
(
k
{\displaystyle k}
的大小不定)
a
1
>
a
2
>
⋯
>
a
k
{\displaystyle a_{1}>a_{2}>\cdots >a_{k))
即分拆的每个数都不相等。生成函數 是
∑
n
=
0
∞
p
(
n
)
x
n
=
∏
k
=
1
∞
(
1
+
x
k
)
{\displaystyle \sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }\left(1+x^{k}\right)}
考虑满足下面条件分拆
a
1
+
a
2
+
⋯
+
a
k
=
n
{\displaystyle a_{1}+a_{2}+\cdots +a_{k}=n}
(
k
{\displaystyle k}
的大小不定)
a
1
≥
a
2
≥
⋯
≥
a
k
{\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{k))
要求
a
i
(
i
=
1
,
2
,
…
,
k
)
{\displaystyle a_{i}(i=1,2,\ldots ,k)}
为奇数 生成函數 是
∑
n
=
0
∞
p
(
n
)
x
n
=
∏
k
=
1
∞
(
1
1
−
x
2
k
−
1
)
{\displaystyle \sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{2k-1))}\right)}
.差分拆的个数与奇分拆的个数是一样多的。
可以通过杨表证明。
當限定將
n
{\displaystyle n}
表示成剛好
k
{\displaystyle k}
個正整數之和時,可以表示為
p
k
(
n
)
{\displaystyle p_{k}(n)}
。顯然,
p
(
n
)
=
∑
k
=
1
n
p
k
(
n
)
{\displaystyle p(n)=\sum _{k=1}^{n}p_{k}(n)}
。
對於
n
>
1
{\displaystyle n>1}
,
p
n
(
n
)
=
p
1
(
n
)
=
1
{\displaystyle p_{n}(n)=p_{1}(n)=1}
p
2
(
n
)
=
⌊
n
2
⌋
{\displaystyle p_{2}(n)=\left\lfloor {\frac {n}{2))\right\rfloor }
(OEIS:A004526 )
p
3
(
n
)
{\displaystyle p_{3}(n)}
= 最接近
n
2
12
{\displaystyle {\frac {n^{2)){12))}
的正整數。(OEIS:A069905 )
p
n
−
1
(
n
)
=
1
{\displaystyle p_{n-1}(n)=1}
p
k
(
n
)
=
p
k
−
1
(
n
−
1
)
+
p
k
(
n
−
k
)
{\displaystyle p_{k}(n)=p_{k-1}(n-1)+p_{k}(n-k)}
不少數學家亦有研究按以下方式分拆的方法數目:
將正整數寫成模p同餘r的正整數之和
將模p同餘r正整數寫成的正整數之和[ 3]