主题
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/

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中被引用

分拆函数 P

引用为

魏斯坦, 埃里克·W. "分拆函数 P." 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/PartitionFunctionP.html

主题分类