主題
Search

分拆函式 P

下載 Mathematica Notebook下載 Wolfram 筆記本

P(n)，有時也記為 p(n) (Abramowitz 和 Stegun 1972, p. 825; Comtet 1974, p. 94; Hardy 和 Wright 1979, p. 273; Conway 和 Guy 1996, p. 94; Andrews 1998, p. 1)，給出將整數 n 寫成正整數之和的方式數，其中加數的順序不被認為是重要的。按照慣例，分拆通常從最大到最小排序 (Skiena 1990, p. 51)。例如，由於 4 可以寫成

4=4
(1)
=3+1
(2)
=2+2
(3)
=2+1+1
(4)
=1+1+1+1,
(5)

因此得出 P(4)=5。P(n) 有時被稱為無限制分拆數，並在 Wolfram 語言中實現為PartitionsP[n]。

對於 P(n)，當 n=1, 2, ..., 時的值為 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ... (OEIS A000041)。對於 P(10^n)，當 n=0, 1, ... 時的值由 1, 42, 190569292, 24061467864032622473692149727991, ... (OEIS A070177) 給出。

P(n) 的前幾個素數值為 2, 3, 5, 7, 11, 101, 17977, 10619863, ... (OEIS A049575)，對應於索引 2, 3, 4, 5, 6, 13, 36, 77, 132, ... (OEIS A046063)。截至 2017 年 2 月 3 日，已知的給出可能素數的最大 n 是 1000007396，具有 35219 位十進位制數字 (E. Weisstein, 2017 年 2 月 12 日)，而已知的給出已證明素數的最大 n 是 221444161，具有 16569 位十進位制數字 (S. Batalov, 2017 年 4 月 20 日； http://primes.utm.edu/top20/page.php?id=54#records)。

PartitionFerrersDiagram

當顯式列出數字 n 的分拆時，最簡單的形式是所謂的自然表示，它簡單地給出表示中的數字序列（例如，對於數字 4=2+1+1，為 (2, 1, 1)）。重數表示則給出每個數字出現的次數以及該數字（例如，對於 4=2·1+1·2，為 (2, 1), (1, 2)）。費勒斯圖是分拆的圖形表示。例如，上面的圖說明了分拆 6+3+3+2+1=15 的 費勒斯圖。

尤拉給出了 P(n) 的生成函式，使用 q-級數

(q)_infty=product_(m=1)^(infty)(1-q^m)
(6)
=sum_(-infty)^(infty)(-1)^nq^(n(3n+1)/2)
(7)
=1-q-q^2+q^5+q^7-q^(12)-q^(15)+q^(22)+q^(26)+....
(8)

這裡，指數是廣義五邊形數 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, ... (OEIS A001318)，並且第 k 項（將 0 計數為第 0 項）的符號為 (-1)^(|_(k+1)/2_|)（其中 |_x_| 是向下取整函式）。然後，分拆數 P(n) 由生成函式給出

1/((q)_infty)=sum_(n=0)^(infty)P(n)q^n
(9)
=1+q+2q^2+3q^3+5q^4+...
(10)

(Hirschhorn 1999)。

將數字 n 分拆為 m 部分的分拆數等於分拆為最大部分為 m 的部分的分拆數，並且分拆為最多 m 部分的分拆數等於分拆為不超過 m 的部分的分拆數。這兩個結果都直接來自注意到費勒斯圖可以按行或按列讀取（雖然預設順序是按行；Hardy 1999, p. 83）。

例如，如果對於所有 a_n=1 n，則尤拉變換 b_n 是將 n 分拆為整數部分的分拆數。

尤拉發明了一個生成函式，它產生 P(n) 的遞推方程，

P(n)=sum_(k=1)^n(-1)^(k+1)[P(n-1/2k(3k-1))+P(n-1/2k(3k+1))]
(11)

(Skiena 1990, p. 57)。其他遞推方程包括

P(2n+1)=P(n)+sum_(k=1)^infty[P(n-4k^2-3k)+P(n-4k^2+3k)]-sum_(k=1)^infty(-1)^k[P(2n+1-3k^2+k)+P(2n+1-3k^2-k)]
(12)

和

P(n)=1/nsum_(k=0)^(n-1)sigma_1(n-k)P(k),
(13)

其中 sigma_1(n) 是除數函式 (Skiena 1990, p. 77; Berndt 1994, p. 108)，以及恆等式

sum_(k=[-(sqrt(24n+1)+1)/6])^(|_(sqrt(24n+1)-1)/6_|)(-1)^kP(n-1/2k(3k+1))=0,
(14)

其中 |_x_| 是向下取整函式，而 [x] 是向上取整函式。

涉及分拆函式 Q 的遞推關係由下式給出

P(n)=sum_(k=0)^(|_n/2_|)Q(n-2k)P(k).
(15)

Atkin 和 Swinnerton-Dyer (1954) 獲得了令人驚訝的恆等式

sum_(n=0)^(infty)P(5n)q^n=product_(n=1)^(infty)((1-q^(5n-3))(1-q^(5n-2))(1-q^(5n)))/((1-q^(5n-4))^2(1-q^(5n-1))^2) (mod 5)
(16)
sum_(n=0)^(infty)P(5n+1)q^n=product_(n=1)^(infty)((1-q^(5n)))/((1-q^(5n-4))(1-q^(5n-1))) (mod 5)
(17)
sum_(n=0)^(infty)P(5n+2)q^n=2product_(n=1)^(infty)((1-q^(5n)))/((1-q^(5n-3))(1-q^(5n-2))) (mod 5)
(18)
sum_(n=0)^(infty)P(5n+3)q^n=3product_(n=1)^(infty)((1-q^(5n-4))(1-q^(5n-1))(1-q^(5n)))/((1-q^(5n-3))^2(1-q^(5n-2))^2) (mod 5)
(19)

(Hirschhorn 1999)。

MacMahon 獲得了優美的遞推關係

P(n)-P(n-1)-P(n-2)+P(n-5)+P(n-7) -P(n-12)-P(n-15)+...=0,
(20)

其中總和是對廣義五邊形數 <=n 求和，並且第 k 項的符號為 (-1)^(|_(k+1)/2_|)，如上所述。拉馬努金在沒有證明的情況下陳述了非凡的恆等式

sum_(k=0)^inftyP(5k+4)q^k=5((q^5)_infty^5)/((q)_infty^6)
(21)

(Darling 1921; Mordell 1922; Hardy 1999, pp. 89-90)，以及

sum_(k=0)^inftyP(7k+5)q^k=7((q^7)_infty^3)/((q)_infty^4)+49q((q^7)_infty^7)/((q)_infty^8)
(22)

(Mordell 1922; Hardy 1999, pp. 89-90, 勘誤已更正)。

Hardy 和 Ramanujan (1918) 使用圓法和模函式獲得了漸近解

P(n)∼1/(4nsqrt(3))e^(pisqrt(2n/3))
(23)

(Hardy 1999, p. 116)，這也由 Uspensky (1920) 獨立發現。Rademacher (1937) 隨後獲得了精確的收斂級數解，該解產生 Hardy-Ramanujan 公式 (23) 作為第一項

P(n)=1/(pisqrt(2))sum_(k=1)^inftyA_k(n)sqrt(k)d/(dn)[(sinh(pi/ksqrt(2/3(n-1/(24)))))/(sqrt(n-1/(24)))],
(24)

其中

A_k(n)=sum_(h=1)^kdelta_(GCD(h,k),1)exp[piisum_(j=1)^(k-1)j/k((hj)/k-|_(hj)/k_|-1/2)-(2piihn)/k],
(25)

delta_(mn) 是克羅內克 delta，而 |_x_| 是向下取整函式 (Hardy 1999, pp. 120-121)。N 項後的餘項是

R(N)<CN^(-1/2)+Dsqrt(N/n)sinh((Ksqrt(n))/N),
(26)

其中 C 和 D 是固定常數 (Apostol 1997, pp. 104-110; Hardy 1999, pp. 121 和 128)。令人驚訝的是，Rademacher 使用的輪廓涉及法雷數列和福特圓 (Apostol 1997, pp. 102-104; Hardy 1999, pp. 121-122)。1942 年，Erdős 表明 Hardy 和 Ramanujan 的公式可以透過初等方法推匯出來 (Hoffman 1998, p. 91)。

Bruinier 和 Ono (2011) 找到了分拆函式 P(n) 的代數公式，作為代數數的有限和，如下所示。定義權重為 2 的亞純模形式 F(z) 為

F(z)=1/2(E_2(z)-2E_2(2z)-3E_2(3z)+6E_2(6z))/(eta^2(z)eta^2(2z)eta^2(3z)eta^3(6z)),
(27)

其中 q=e^(2piiz), E_2(q) 是一個艾森斯坦級數，而 eta(q) 是一個戴德金 eta 函式。現在定義

R(z)=-(1/(2pii)d/(dz)+1/(2piy))F(z),
(28)

其中 z=x+iy。此外，令 Q_n 為積分二元二次型 Q(x,y)=ax^2+bxy+cy^2 的等價類的一組代表，使得 6|a，其中 a>0 且 b=1 (mod 12)，並且對於每個 Q(x,y)，令 alpha_Q 為上半平面中的所謂 CM 點，對於該點 Q(alpha_Q,1)=0。那麼

P(n)=(Tr(n))/(24n-1),
(29)

其中跡定義為

Tr(n)=sum_(Q in Q_n)R(alpha_Q).
(30)

拉馬努金髮現了許多分拆函式 P 同餘。

令 f_O(x) 為僅包含奇數的分拆 P_O(n) 的生成函式，而令 f_D(x) 為沒有重複的分拆 P_D(n) 的生成函式，則

f_O(x)=f_D(x)
(31)
=product_(k=1,3,...)^(infty)sum_(i=0)^(infty)x^(ik)
(32)
=1/(product_(k=1,3,...)^(infty)1-x^k)
(33)
=product_(k=1)^(infty)(1+x^k)
(34)
=1/2(-q;x)_infty
(35)
=1+x+x^2+2x^3+2x^4+3x^5+...,
(36)

正如尤拉發現的那樣 (Honsberger 1985; Andrews 1998, p. 5; Hardy 1999, p. 86)，給出 P_O(n)=P_D(n) 對於 n=0, 1, ... 的前幾個值為 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (OEIS A000009)。恆等式

product_(k=1)^infty(1+z^k)=product_(k=1)^infty(1-z^(2k-1))^(-1)
(37)

被稱為尤拉恆等式 (Hardy 1999, p. 84)。

將不等部分分拆為偶數部分的分拆數與將不等部分分拆為奇數部分的分拆數之差的生成函式由下式給出

product_(k=1)^(infty)(1-z^k)=1-z-z^2+z^5+z^7-z^(12)-z^(15)+...
(38)
=1+sum_(k=1)^(infty)c_kz^k,
(39)

其中

c_k={(-1)^n for k of the form 1/2n(3n+/-1); 0 otherwise.
(40)

令 P_E(n) 為僅分拆偶數的分拆數，令 P_(EO)(n) (P_(DO)(n)) 為部分都是偶數（奇數）且都不同的分拆數。那麼 P_(DO)(n) 的生成函式由下式給出

f_(DO)(x)=product_(k=1,3,...)^(infty)1+x^k
(41)
=(-x;x^2)_infty
(42)

(Hardy 1999, p. 86)，並且前幾個值為 1, 1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, ... (OEIS A000700)。Honsberger (1985, pp. 241-242) 給出了其他生成函式。

令人驚奇的是，沒有重複偶數部分的分拆數與沒有部分出現超過三次的分拆數相同，也與沒有部分可被 4 整除的分拆數相同，所有這些都共享生成函式

P_3(n)=product_(k=1)^(infty)(1+x^(2k))/(1-x^(2k-1))
(43)
=product_(k=1)^(infty)(1+x^k+x^(2k)+x^(3k))
(44)
=product_(k=1)^(infty)(1-x^(4k))/(1-x^k)
(45)
=((x^4)_infty)/((x)_infty).
(46)

P^*(n) 的前幾個值為 1, 2, 3, 4, 6, 9, 12, 16, 22, 29, 38, ... (OEIS A001935; Honsberger 1985, pp. 241-242)。

一般來說，沒有部分出現超過 d 次的分拆數的生成函式為

P_d(n)=product_(k=1)^(infty)sum_(i=0)^(d)x^(ik)
(47)
=product_(k=1)^(infty)(1-x^((d+1)k))/(1-x^k)
(48)

(Honsberger 1985, pp. 241-242)。每個部分出現 2、3 或 5 次的分拆數的生成函式為

P_(2,3,5)(n)=product_(k=1)^(infty)(1+x^(2k)+x^(3k)+x^(5k))
(49)
=product_(k=1)^(infty)(1+x^(2k))(1+x^(3k))
(50)
=product_(k=1)^(infty)(1-x^(4k))/(1-x^(2k))(1-x^(6k))/(1-x^(3k))
(51)
=((x^4)_infty(x^6)_infty)/((x^2)_infty(x^3)_infty).
(52)

前幾個值為 0, 1, 1, 1, 1, 3, 1, 3, 4, 4, 4, 8, 5, 9, 11, 11, 12, 20, 15, 23, ... (OEIS A089958; Honsberger 1985, pp. 241-242)。

沒有部分恰好出現一次的分拆數為

P_1(n)=product_(k=1)^(infty)(1+x^(2k)+x^(3k)+...)
(53)
=product_(k=1)^(infty)(1-x^k+x^(2k))/(1-x^k)
(54)
=product_(k=1)^(infty)(1+x^(3k))/(1-x^(2k))
(55)
=product_(k=1)^(infty)(1-x^(6k))/((1-x^(2k))(1-x^(3k)))
(56)
=product_(k=1)^(infty)((x^6)_infty)/((x^2)_infty(x^3)_infty).
(57)

前幾個值為 1, 0, 1, 1, 2, 1, 4, 2, 6, 5, 9, 7, 16, 11, 22, 20, 33, 28, 51, 42, 71, ... (OEIS A007690; Honsberger 1985, p. 241, 更正了方程 57 中的符號錯誤)。

從這些推匯出來的一些附加的有趣定理（Honsberger 1985, pp. 64-68 和 143-146）是

1. 沒有偶數部分重複的 n 的分拆數與沒有部分出現超過三次的 n 的分拆數相同，也與沒有部分可被 4 整除的分拆數相同。

2. 沒有部分出現次數超過 n 的分拆數與沒有項是 d 的倍數的 d+1 的分拆數相同。

3. 每個部分出現 2、3 或 5 次的 n 的分拆數與每個部分同餘於 12 模 2、3、6、9 或 10 的分拆數相同。

4. 沒有部分恰好出現一次的 n 的分拆數與沒有部分同餘於 6 模 1 或 5 的 n 的分拆數相同。

5. 部分都是偶數且不同的分拆數等於具有奇數部分和偶數部分的分拆數的絕對差值。

P(n) 滿足不等式

P(n)<=1/2[P(n+1)+P(n-1)]
(58)

(Honsberger 1991)。

P(n,k) 表示將 n 寫成恰好 k 項之和的方式數，或者等效地，分拆為最大部分恰好為 k 的部分的分拆數。（請注意，如果將“恰好 k”更改為“k 或更少”，並將“最大部分恰好為 k，”更改為“沒有元素大於 k”，則獲得分拆函式 q。）例如，P(5,3)=2，因為長度為 3 的 5 的分拆為 {3,1,1} 和 {2,2,1}，並且最大元素為 3 的 5 的分拆為 {3,2} 和 {3,1,1}。

這些 P(n,k) 分拆可以使用 Wolfram 語言中的IntegerPartitions[n, {k}]。

P(n,k) 可以從遞推關係計算得出

P(n,k)=P(n-1,k-1)+P(n-k,k)
(59)

(Skiena 1990, p. 58; Ruskey) 其中 P(n,k)=0 對於 k>n, P(n,n)=1, 和 P(n,0)=0。P(k,n) 的三角形由下式給出

1 1 1 1 1 1 1 2 1 1 1 2 2 1 1 1 3 3 2 1 1
(60)

(OEIS A008284)。最大部分為 n 的 k 的分拆數與 P(n,k) 相同。

遞推關係可以精確求解，得到

P(n,1)=1
(61)
P(n,2)=1/4[2n-1+(-1)^n]
(62)
P(n,3)=1/(72)[6n^2-7-9(-1)^n+16cos(2/3pin)]
(63)
P(n,4)=1/(864){3(n+1)[2n(n+2)-13+9(-1)^n]-96cos(2/3npi)+108(-1)^(n/2)mod(n+1,2)+32sqrt(3)sin(2/3npi)},
(64)

其中 P(n,k)=0 對於 n<k。函式 P(n,k) 也可以為 k 的前幾個值顯式給出，形式簡單

P(n,2)=|_1/2n_|
(65)
P(n,3)=[1/(12)n^2],
(66)

其中 |_x_| 是向下取整函式，而 [x] 是最接近整數函式 (Honsberger 1985, pp. 40-45)。B. Schwennicke 的類似處理定義了

t_k(n)=n+1/4k(k-3)
(67)

然後產生

P(n,2)=[1/2t_2(n)]
(68)
P(n,3)=[1/(12)t_3^2(n)]
(69)
P(n,4)={[1/(144)t_4^3(n)-1/(48)t_4(n)] for n even; [1/(144)t_4^3(n)-1/(12)t_4(n)] for n odd.
(70)

Hardy 和 Ramanujan (1918) 獲得了精確的漸近公式

P(n)=sum_(k<alphasqrt(n))P_k(n)+O(n^(-1/4)),
(71)

其中 alpha 是一個常數。然而，總和

sum_(k=1)^inftyP_k(n)
(72)

發散，正如 Lehmer (1937) 首次證明的那樣。

另請參閱

Alcuin 序列, 共軛分拆, Elder 定理, 尤拉恆等式, 費勒斯圖, Göllnitz 定理, 分拆, 分拆函式 P 同餘, 分拆函式 q, 分拆函式 Q, 五邊形數, 五邊形數定理, 平面分拆, 隨機分拆, Rogers-Ramanujan 恆等式, 自共軛分拆, Stanley 定理, 平方和函式, Tau 函式

相關 Wolfram 站點

http://functions.wolfram.com/IntegerFunctions/PartitionsP/

使用 探索

參考文獻

Abramowitz, M. 和 Stegun, I. A. (編輯). "Unrestricted Partitions." §24.2.1 in 數學函式手冊，包含公式、圖表和數學表格，第 9 版。 New York: Dover, p. 825, 1972.Adler, H. "Partition Identities--From Euler to the Present." Amer. Math. Monthly 76, 733-746, 1969.Adler, H. "The Use of Generating Functions to Discover and Prove Partition Identities." Two-Year College Math. J. 10, 318-329, 1979.Andrews, G. E. 分拆理論。 Cambridge, England: Cambridge University Press, 1998.Apostol, T. M. Ch. 4 in 解析數論導論。 New York: Springer-Verlag, 1976.Apostol, T. M. "Rademacher's Series for the Partition Function." Ch. 5 in 模函式與狄利克雷級數在數論中的應用，第 2 版。 New York: Springer-Verlag, pp. 94-112, 1997.Atkin, A. O. L. 和 Swinnerton-Dyer, P. "Some Properties of Partitions." Proc. London Math. Soc. 4, 84-106, 1954.Berndt, B. C. 拉馬努金筆記本，第四部分。 New York: Springer-Verlag, 1994.Bruinier, J. H. 和 Ono, K. "Algebraic Formulas for the Coefficients of Half-Integral Weight Harmonic Weak Maass Forms." http://arxiv.org/abs/1104.1182/. 2011 年 4 月 6 日.Comtet, L. 高階組合數學：有限與無限展開的藝術，修訂擴增版。 Dordrecht, Netherlands: Reidel, p. 307, 1974.Conway, J. H. 和 Guy, R. K. 數字之書。 New York: Springer-Verlag, pp. 94-96, 1996.Darling, H. B. C. "Proofs of Certain Identities and Congruences Enunciated by S. Ramanujan." Proc. London Math. Soc. 19, 350-372, 1921.David, F. N.; Kendall, M. G.; 和 Barton, D. E. 對稱函式及相關表格。 Cambridge, England: Cambridge University Press, p. 219, 1966.Gupta, H. "A Table of Partitions." Proc. London Math. Soc. 39, 142-149, 1935.Gupta, H. "A Table of Partitions (II)." Proc. London Math. Soc. 42, 546-549, 1937.Gupta, H.; Gwyther, A. E.; 和 Miller, J. C. P. 英國皇家學會數學表，第 4 卷：分拆表。 London: Cambridge University Press, 1958.Hardy, G. H. "Ramanujan's Work on Partitions" 和 "Asymptotic Theory of Partitions." Chs. 6 和 8 in 拉馬努金：關於其生平和工作啟發的十二講座，第 3 版。 New York: Chelsea, pp. 83-100 和 113-131, 1999.Hardy, G. H. 和 Ramanujan, S. "Asymptotic Formulae in Combinatory Analysis." Proc. London Math. Soc. 17, 75-115, 1918.Hardy, G. H. 和 Wright, E. M. 數論導論，第 5 版。 Oxford, England: Clarendon Press, 1979.Hirschhorn, M. D. "Another Short Proof of Ramanujan's Mod 5 Partition Congruences, and More." Amer. Math. Monthly 106, 580-583, 1999.Hoffman, P. 唯愛數字的人：保羅·埃爾德什的故事和對數學真理的探索。 New York: Hyperion, 1998.Honsberger, R. 數學珍寶 III。 Washington, DC: Math. Assoc. Amer., pp. 40-45 和 64-68, 1985.Honsberger, R. 更多數學拾零。 Washington, DC: Math. Assoc. Amer., pp. 237-239, 1991.Jackson, D. 和 Goulden, I. 組合計數。 New York: Academic Press, 1983.Lehmer, D. H. "On the Hardy-Ramanujan Series for the Partition Function." J. London Math. Soc. 12, 171-176, 1937.Lehmer, D. H. "On a Conjecture of Ramanujan." J. London Math. Soc. 11, 114-118, 1936.Lehmer, D. H. "The Series for the Partition Function." Trans. Amer. Math. Soc. 43, 271-295, 1938.Lehmer, D. H. "On the Remainders and Convergence of the Series for the Partition Function." Trans. Amer. Math. Soc. 46, 362-373, 1939.MacMahon, P. A. "Note of the Parity of the Number which Enumerates the Partitions of a Number." Proc. Cambridge Philos. Soc. 20, 281-283, 1921.MacMahon, P. A. "The Parity of p(n), the Number of Partitions of n, when n<=1000." J. London Math. Soc. 1, 225-226, 1926.MacMahon, P. A. 組合分析。 New York: Chelsea, 1960.Mordell, L. J. "Note on Certain Modular Relations Considered by Messrs Ramanujan, Darling and Rogers." Proc. London Math. Soc. 20, 408-416, 1922.Rademacher, H. "Zur Theorie der Modulfunktionen." J. reine angew. Math. 167, 312-336, 1932.Rademacher, H. "On the Partition Function p(n)." Proc. London Math. Soc. 43, 241-254, 1937.Rademacher, H. "On the Expansion of the Partition Function in a Series." Ann. Math. 44, 416-422, 1943.Ruskey, F. "Information of Numerical Partitions." http://www.theory.csc.uvic.ca/~cos/inf/nump/NumPartition.html.Skiena, S. 使用 Mathematica 實現離散數學：組合學和圖論。 Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequences A000009/M0281, A000041/M0663, A000700/M0217, A001318/M1336, A001935/M0566, A007690/M0167, A008284, A046063, A049575, A070177, A089958 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. 和 Plouffe, S. 整數數列百科全書。 San Diego, CA: Academic Press, 1995.Uspensky, J. V. "Asymptotic Formulae for Numerical Functions Which Occur in the Theory of Partitions.' Bull. Acad. Sci. URSS 14, 199-218, 1920.

在 中被引用

分拆函式 P

引用為

魏斯坦, 埃裡克·W. "分拆函式 P." 來自 ——Wolfram 網路資源。 https://mathworld.tw/PartitionFunctionP.html

主題分類