關於將整數寫成其他整數的乘積,請見「
整數分解」。
| 此條目需要 精通或熟悉相關主題的編者參與及協助編輯。 (2013年12月31日) 請邀請適合的人士改善本條目。更多的細節與詳情請參見討論頁。 |
一個正整數可以寫成一些正整數的和。在數論上,跟這些和式有關的問題稱為整數拆分、整數剖分、整數分割、分割數或切割數(英語:Integer partition)。其中最常見的問題就是給定正整數
,求不同數組
的數目,符合下面的條件:
(
的大小不定)
![{\displaystyle a_{1}\geq a_{2}\geq ...\geq a_{k}>0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/afcd1b821b14e9331769f190524453d2b0f914d2)
- 其他附加條件(例如限定「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圖示是將第1行放
個方格,第2行放
個方格……第
行放
個方格,來表示整數分割的其中一個方法。
藉助Ferrers圖示,可以推導出許多恆等式:
- 給定正整數k和n,n表達成不多於k個正整數之和的方法數目,等於將n分割成任意個不大於k的正整數之和的方法數目。
證明:將表示前者其中一個數組的Ferrers圖示沿對角線反射,便得到後者的一個數組。即兩者一一對應,因此其數目相同。
例如 k=3,n=6:
此外,
![{\displaystyle 6=1+5=1+1+1+1+2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b1221efc065379db8c990ba83ad5e94999fce4c3)
![{\displaystyle 6=2+4=2+2+1+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3efc19b87bc0561b008ed288fdb7f929e9edb930)
![{\displaystyle 6=3+3=2+2+2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05c2349bef8bd9dd75081c1c6dfdd09e722a7add)
![{\displaystyle 6=6=1+1+1+1+1+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1433e89b0a0efdf375ea8058704d7812441c5864)
- 上述恆等式的值亦等於將
表達成剛好
個正整數之和的方法的數目。
- 給定正整數
。將
表達成兩兩相異正整數之和的方法的數目,等於將
表達成奇數之和的方法的數目。
例如
:
- 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
- 將
表達成
個1和
個2之和,這些方法的數目是第
個斐波那契數。
- 將
表達成多於1的正整數之和的方法數目是p(n) - p(n-1)。
的生成函數是
![{\displaystyle \sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{k}}}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c1e1325c16d6a04da6f2a4fc63446c8dc5f55be0)
當|x|<1,右邊可寫成:
![{\displaystyle (1+x+x^{2}+x^{3}+...)(1+x^{2}+x^{4}+x^{6}+...)(1+x^{3}+x^{6}+...)...}](https://wikimedia.org/api/rest_v1/media/math/render/svg/971838305763b3ea967c6f5f3059b4725ae983c3)
生成函數的倒數為歐拉函數,利用五邊形數定理可得到以下的展開式:
![{\displaystyle \prod _{k=1}^{\infty }(1-x^{k})=\sum _{i=-\infty }^{\infty }(-1)^{i}x^{i(3i-1)/2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15f47a671c5dc26f36cc88f9eab2b4ee6e38600c)
將
生成函數配合五邊形數定理,可以得到以下的遞歸關係式
![{\displaystyle p(n)=\sum _{i}(-1)^{i-1}p(n-q_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89d2907100f525090adfbaeca230d7c7e74f37b3)
其中
是第
個廣義五邊形數。
一個 (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。
漸近式:
![{\displaystyle p(n)\sim {\frac {\exp \left(\pi {\sqrt {2n/3}}\right)}{4n{\sqrt {3}}}}{\mbox{ as }}n\rightarrow \infty .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8b755f8c37623693cc5bcbfec444f1a2033fc4e)
這式子是1918年哈代和拉馬努金,以及1920年J. V. Uspensky獨立發現的。
1937年,Hans Rademacher得出一個更佳的結果:
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d592ebc031ef0826b9457d3df2470bc2acac7f1c)
其中
。
表示
互質時才計算那項。
表示戴德金和。這條公式的證明用上了和戴德金η函數、福特圓、法里數列、模群。
在將
表示成正整數之和的所有和式之中,任意正整數
作為和項出現在這些式子內的次數,跟每條和式中出現
次或以上的正整數數目,相同。
當
時,此定理又稱為Stanley定理。[1][2]
以
為例:
- 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。
以下敘述帶有附加條件的分拆。
考慮滿足下面條件分拆
(
的大小不定)
即分拆的每個數都不相等。
生成函數是
![{\displaystyle \sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }\left(1+x^{k}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22a005704559e9a4d7584d304ca92d625ac95686)
考慮滿足下面條件分拆
(
的大小不定)
![{\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efa16a668afd1abb2d79bff2b7b56b36a9672db3)
- 要求
為奇數
生成函數是
.
差分拆的個數與奇分拆的個數是一樣多的。
可以通過楊表證明。
當限定將
表示成剛好
個正整數之和時,可以表示為
。顯然,
。
- 對於
,![{\displaystyle p_{n}(n)=p_{1}(n)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70dfccc1f390aef4d2ce6edae8a33bf4d6fad6eb)
(OEIS:A004526)
= 最接近
的正整數。(OEIS:A069905)
![{\displaystyle p_{n-1}(n)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/def3169725693cee41f8c7a92364e0eab26839f0)
![{\displaystyle p_{k}(n)=p_{k-1}(n-1)+p_{k}(n-k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1102e421c2415d5ec0165c802c52b10734489576)
不少數學家亦有研究按以下方式分拆的方法數目:
- 將正整數寫成模p同餘r的正整數之和
- 將模p同餘r正整數寫成的正整數之和[3]