This article needs more work.
Please help by expanding it!
The
partition function gives the number of
partitions of a
nonnegative integer into
positive integers. (There is one partition of zero into positive integers, i.e. the empty partition, since the
empty sum is defined as
0.)
Table of partition function approximations
Note that
p (n) = F (n + 1), 0 ≤ n ≤ 4 |
, where
is the
th Fibonacci number. For the
Hardy–Ramanujan asymptotic approximation,
is the
nearest integer function.
Partition function approximations
|
.
|
Hardy–Ramanujan asymptotic approximation
|
.
|
|
|
A000041 .
|
A190840 .
|
|
A035949 .
|
< 0
|
0
|
|
|
|
0
|
1
|
|
|
|
1
|
1
|
2
|
1
|
|
2
|
2
|
3
|
1
|
|
3
|
3
|
4
|
1
|
|
4
|
5
|
6
|
1
|
0
|
5
|
7
|
9
|
2
|
1
|
6
|
11
|
13
|
2
|
1
|
7
|
15
|
18
|
3
|
2
|
8
|
22
|
26
|
4
|
2
|
9
|
30
|
35
|
5
|
4
|
10
|
42
|
48
|
6
|
4
|
11
|
56
|
65
|
9
|
7
|
12
|
77
|
87
|
10
|
8
|
13
|
101
|
115
|
14
|
12
|
14
|
135
|
152
|
17
|
14
|
15
|
176
|
199
|
23
|
20
|
16
|
231
|
258
|
27
|
23
|
17
|
297
|
333
|
36
|
32
|
18
|
385
|
427
|
42
|
39
|
19
|
490
|
545
|
55
|
51
|
20
|
627
|
692
|
65
|
61
|
21
|
792
|
875
|
83
|
80
|
22
|
1002
|
1102
|
100
|
95
|
23
|
1255
|
1381
|
126
|
122
|
24
|
1575
|
1725
|
150
|
146
|
25
|
1958
|
2145
|
187
|
183
|
26
|
2436
|
2659
|
223
|
219
|
27
|
3010
|
3285
|
275
|
273
|
28
|
3718
|
4046
|
328
|
324
|
29
|
4565
|
4967
|
402
|
399
|
30
|
5604
|
6080
|
476
|
475
|
31
|
6842
|
7423
|
581
|
578
|
32
|
8349
|
9037
|
688
|
685
|
33
|
10143
|
10974
|
831
|
830
|
34
|
12310
|
13293
|
983
|
979
|
35
|
14883
|
16065
|
1182
|
1177
|
36
|
17977
|
19370
|
1393
|
1387
|
37
|
21637
|
23304
|
1667
|
1655
|
38
|
26015
|
27977
|
1962
|
1945
|
39
|
31185
|
33519
|
2334
|
2311
|
40
|
37338
|
40080
|
2742
|
2705
|
41
|
44583
|
47833
|
3250
|
3198
|
42
|
53174
|
56981
|
3807
|
3737
|
43
|
63261
|
67757
|
4496
|
4396
|
44
|
75175
|
80431
|
5256
|
5121
|
45
|
89134
|
95316
|
6182
|
6003
|
46
|
105558
|
112771
|
7213
|
6973
|
47
|
124754
|
133211
|
8457
|
8143
|
48
|
147273
|
157115
|
9842
|
9439
|
49
|
173525
|
185031
|
11506
|
10981
|
50
|
204226
|
217590
|
13364
|
12697
|
The following table (compiled in OpenOffice.org Calc, wich has 15 digits max precision, implying that the last digit or two of 14 or 15 digits numbers is not reliable) compares two asymptotic approximations of
, where the first one is the Hardy–Ramanujan asymptotic approximation. (I got the
ROUND( EXP(PI()*SQRT(2*n/3)) / (4*(n+(1/2)*(LOG(n))^3)*SQRT(3)) )
(also asymptotic) approximation empirically. If both asymptotic approximations are always overestimates of
, then
HR2(n)
is always a better approximation than
HR(n)
, since
HR2(n)
is always less than
HR(n)
. Thus arises the question: are
HR(n)
and
HR2(n)
always overstimates of
? —
Daniel Forgues 20:39, 31 July 2011 (UTC))
n p(n) HR(n) HR(n) – p(n) HR2(n) HR2(n) – p(n) (HR2(n) – p(n))
A000041 Hardy-Ramanujan (Modified) Hardy-Ramanujan /
asymptotic (also) asymptotic (HR(n) – p(n))
approximation of p(n) approximation of p(n)
ROUND( EXP(PI()*SQRT(2*n/3)) ROUND( EXP(PI()*SQRT(2*n/3))
/ /
(4*(n)*SQRT(3)) ) (4*(n+(1/2)*(LOG(n))^3)*SQRT(3)) )
5 7 9 2 9 2 1
10 42 48 6 46 4
15 176 199 23 188 12
20 627 692 65 656 29
25 1,958 2,145 187 2,034 76 0.4064171122994
30 5,604 6,080 476 5,770 166
35 14,883 16,065 1,182 15,262 379
40 37,338 40,080 2,742 38,121 783
45 89,134 95,316 6,182 90,759 1,625
50 204,226 217,590 13,364 207,419 3,193 0.2389254714157
55 451,276 479,431 28,155 457,506 6,230
60 966,467 1,024,004 57,537 978,175 11,708
65 2,012,558 2,127,604 115,046 2,034,361 21,803
70 4,087,968 4,312,670 224,702 4,127,481 39,513
75 8,118,264 8,549,010 430,746 8,189,102 70,838 0.1644542259243
80 15,796,476 16,606,782 810,306 15,920,936 124,460
85 30,167,357 31,667,409 1,500,052 30,383,686 216,329
90 56,634,173 59,367,760 2,733,587 57,004,184 370,011
95 104,651,419 109,564,225 4,912,806 105,277,945 626,526
100 190,569,292 199,280,893 8,711,601 191,616,244 1,046,952 0.1201790577874
105 342,325,709 357,586,938 15,261,229 344,058,910 1,733,201
110 607,163,746 633,589,186 26,425,440 610,001,367 2,837,621
115 1,064,144,451 1,109,412,780 45,268,329 1,068,750,525 4,606,074
120 1,844,349,560 1,921,105,572 76,756,012 1,851,755,110 7,405,550
125 3,163,127,352 3,292,035,176 128,907,824 3,174,941,068 11,813,716 0.0916446778280
130 5,371,315,400 5,585,841,896 214,526,496 5,390,004,417 18,689,017
135 9,035,836,076 9,389,797,022 353,960,946 9,065,191,305 29,355,229
140 15,065,878,135 15,645,130,511 579,252,376 15,111,647,413 45,769,278
145 24,908,858,009 25,849,469,513 940,611,504 24,979,755,750 70,897,741
150 40,853,235,313 42,369,336,269 1,516,100,956 40,962,334,140 109,098,827 0.0719601333725
155 66,493,182,097 68,919,680,135 2,426,498,038 66,660,068,881 166,886,784
160 107,438,159,466 111,295,547,185 3,857,387,719 107,691,928,166 253,768,700
165 172,389,800,255 178,482,384,132 6,092,583,877 172,773,583,796 383,783,541
170 274,768,617,130 284,332,114,132 9,563,497,002 275,345,904,405 577,287,275
175 435,157,697,830 450,080,578,578 14,922,880,748 436,021,721,915 864,024,085 0.0578992822894
180 684,957,390,936 708,110,435,576 23,153,044,640 686,244,237,116 1,286,846,180
185 1,071,823,774,337 1,107,549,520,159 35,725,745,822 1,073,731,572,223 1,907,797,886
190 1,667,727,404,093 1,722,562,621,633 54,835,217,540 1,670,543,118,819 2,815,714,726
195 2,580,840,212,973 2,664,579,377,303 83,739,164,330 2,584,978,391,028 4,138,178,055
200 3,972,999,029,388 4,100,251,432,188 127,252,402,800 3,979,055,824,394 6,056,795,006 0.0475967044451
205 6,085,253,859,260 6,277,716,787,260 192,462,928,000 6,094,084,357,824 8,830,498,564
210 9,275,102,575,355 9,564,864,314,565 289,761,739,210 9,287,928,415,566 12,825,840,211
215 14,070,545,699,287 14,504,870,558,863 434,324,859,576 14,089,107,769,612 18,562,070,325
220 21,248,279,009,367 21,896,510,200,516 648,231,191,149 21,275,049,463,813 26,770,454,446
225 31,946,390,696,157 32,909,878,835,929 963,488,139,772 31,984,871,555,578 38,480,859,421 0.0399391106465
230 47,826,239,745,920 49,252,568,636,892 1,426,328,890,972 47,881,376,419,261 55,136,673,341
235 71,304,185,514,919 73,407,495,709,204 2,103,310,194,285 71,382,945,468,515 78,759,953,596
240 105,882,246,722,733 108,972,168,902,833 3,089,922,180,100 105,994,418,678,409 112,171,955,676
245 156,618,412,527,946 161,141,141,284,870 4,522,728,756,924 156,777,718,615,992 159,306,088,046
250 230,793,554,364,681 237,389,967,288,174 6,596,412,923,493 231,019,181,853,355 225,627,488,674 0.0342045731962
Table of related formulae and values
Partition function related formulae and values
|
A000041
|
Differences
A002865
|
Partial sums
A000070
|
Partial sums of reciprocals
|
< 0
|
0
|
0
|
0
|
|
0
|
1
|
1
|
1
|
|
1
|
1
|
0
|
2
|
|
2
|
2
|
1
|
4
|
|
3
|
3
|
1
|
7
|
|
4
|
5
|
2
|
12
|
|
5
|
7
|
2
|
19
|
|
6
|
11
|
4
|
30
|
|
7
|
15
|
4
|
45
|
|
8
|
22
|
7
|
67
|
|
9
|
30
|
8
|
97
|
|
10
|
42
|
12
|
139
|
|
11
|
56
|
14
|
195
|
|
12
|
77
|
21
|
272
|
|
13
|
101
|
24
|
373
|
|
14
|
135
|
34
|
508
|
|
15
|
176
|
41
|
684
|
|
16
|
231
|
55
|
915
|
|
17
|
297
|
66
|
1212
|
|
18
|
385
|
88
|
1597
|
|
19
|
490
|
105
|
2087
|
|
20
|
627
|
137
|
2714
|
|
21
|
792
|
165
|
3506
|
|
22
|
1002
|
210
|
4508
|
|
23
|
1255
|
253
|
5763
|
|
24
|
1575
|
320
|
7338
|
|
25
|
1958
|
383
|
9296
|
|
26
|
2436
|
478
|
11732
|
|
27
|
3010
|
574
|
14742
|
|
28
|
3718
|
708
|
18460
|
|
29
|
4565
|
847
|
23025
|
|
30
|
5604
|
1039
|
28629
|
|
31
|
6842
|
1238
|
35471
|
|
32
|
8349
|
1507
|
43820
|
|
33
|
10143
|
1794
|
53963
|
|
34
|
12310
|
2167
|
66273
|
|
35
|
14883
|
2573
|
81156
|
|
36
|
17977
|
3094
|
99133
|
|
37
|
21637
|
3660
|
120770
|
|
38
|
26015
|
4378
|
146785
|
|
39
|
31185
|
5170
|
177970
|
|
40
|
37338
|
6153
|
215308
|
|
41
|
44583
|
7245
|
259891
|
|
42
|
53174
|
8591
|
313065
|
|
43
|
63261
|
10087
|
376326
|
|
44
|
75175
|
11914
|
451501
|
|
45
|
89134
|
13959
|
540635
|
|
46
|
105558
|
16424
|
646193
|
|
47
|
124754
|
19196
|
770947
|
|
48
|
147273
|
22519
|
918220
|
|
49
|
173525
|
26252
|
1091745
|
|
50
|
204226
|
30701
|
1295971
|
|
Generating function of the partition function
The
generating function of
is the
reciprocal of
Euler’s function
![{\displaystyle G_{\{p(n)\}}(x)=\sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{k}}}\right)={\frac {1}{\prod _{k=1}^{\infty }(1-x^{k})}}.}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a6fd6e5f3b74b2c79eca02eba89347cd2d0db700)
Asymptotic behavior of the partition function
An
asymptotic formula, first obtained by
G. H. Hardy and
Ramanujan in 1918 and independently by
J. V. Uspensky in 1920, for
is given by
![{\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}~e^{\pi {\sqrt {\frac {2n}{3}}}}={\frac {1}{8n\sin({\frac {\pi }{3}})}}~e^{{\frac {\pi }{3}}\sin({\frac {\pi }{3}}){\sqrt {8n}}}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/830237bb24afb4c1da8c4aba6bc738d212f29ca6)
where
is
Gelfond’s constant.
Partition function formula
The
partition function , is given by
[1]
![{\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }A_{k}(n)~k^{\frac {1}{2}}{\Bigg [}{\frac {d}{dx}}{\frac {\sinh {\bigg (}{\frac {\pi }{k}}{\big (}{\frac {2}{3}}{\big )}^{\frac {1}{2}}{\big (}x-{\frac {1}{24}}{\big )}^{\frac {1}{2}}{\bigg )}}{{\big (}x-{\frac {1}{24}}{\big )}^{\frac {1}{2}}}}{\Bigg ]}_{x=n},\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/21cc7215f3b39d549d504f048dd42a9fa829f308)
where
is an explicitly given finite sum of
24th roots of unity.
Note that
when
since a
negative integer is not the sum of
positive integers, and
since the
empty partition gives the
empty sum, defined as the
additive identity, i.e.
0.
Partition function recurrence
Euler’s pentagonal number theorem begets a finite (since
for
)
recursive formula for the
partition function
![{\displaystyle p(n)=\sum _{j=1}^{\infty }(-1)^{j-1}[p(n-q_{j})+p(n-q_{-j})]=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-\cdots \,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f288d2fe2c0c98a25064826da4519ee2169c0868)
where
are the
generalized pentagonal numbers, with
going through the integer sequence (
A001057)
-
{0, 1, −1, 2, −2, 3, −3, 4, − 4, 5, −5, 6, − 6, 7, −7, 8, −8, 9, − 9, 10, −10, 11, −11, 12, −12, 13, −13, 14, −14, 15, −15, 16, −16, 17, −17, 18, −18, 19, −19, 20, −20, 21, −21, 22, −22, 23, −23, 24, −24, 25, −25, 26, −26, ...}
giving the sequence of
generalized pentagonal numbers (
A001318)
-
{0, 1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100, 117, 126, 145, 155, 176, 187, 210, 222, 247, 260, 287, 301, 330, 345, 376, 392, 425, 442, 477, 495, 532, 551, 590, 610, 651, 672, 715, ...}
The recurrence may be expressed with explicit finite bounds for the summation indexes
![{\displaystyle p(n)=\sum _{j=1}^{{\big \lfloor }{\tfrac {1+{\sqrt {1+24n}}}{6}}{\big \rfloor }}(-1)^{j-1}~p{\big (}n-{\tfrac {j(3j-1)}{2}}{\big )}+\sum _{j=1}^{{\big \lfloor }{\tfrac {-1+{\sqrt {1+24n}}}{6}}{\big \rfloor }}(-1)^{j-1}~p{\big (}n-{\tfrac {j(3j+1)}{2}}{\big )}\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ae9d0ab5e17807b2c66c729ba8c93e11ac148c83)
Intermediate partition function
The number of partitions of
using only
positive integers at least as large as
, called the
intermediate partition function , is given by
![{\displaystyle p(k,n)=?,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/326321824cf69432e8882e4b09ac9e1aa0c753e7)
where
when
or
, and
since the
empty partition gives the
empty sum (the
additive identity,
0).
Intermediate partition function formula
The intermediate partition function formula is
![{\displaystyle p(n)=1+\sum _{i=1}^{\lfloor {\frac {n}{2}}\rfloor }p(i,n-i)\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/0dce8729b92254fd78b4584ea3b8ee306a167825)
where we have the
empty sum (the
additive identity,
0) for the summation when
, thus giving
.
Intermediate partition function formula (other version)
The partition function may be expressed in terms of the intermediate partition function trivially as
![{\displaystyle p(n)=p(1,n),\,n\,\geq \,0,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/09d1474f42e6f9650230366dfe9afaa4ae6cf7bf)
and since every partition of
with smallest part
1 is trivially obtained from the partition of
without that part
1, we have
and by recursion we get
![{\displaystyle p(0)=1,\,p(n)=[p(n-2)+p(2,n-1)]+p(2,n),\,n\,\geq \,1,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/6247a84a2c32c3a290f7fa401e81200385677153)
...
![{\displaystyle p(0)=1,\,p(n)=[p(n-3)+p(2,n-2)]+p(2,n-1)+p(2,n),\,n\,\geq \,1,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/48e9061074799e388a23f21f135a5c52bcc3737b)
...
![{\displaystyle p(0)=1,\,p(n)=p(0)+\sum _{i=1}^{n}p(2,i),\,n\,\geq \,1,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/5c9474d079e7eba6b4caa72c5ffb5f66dde4cd2d)
which may be rewritten as (where
since the
empty partition gives the
empty sum, i.e. the
additive identity,
0)
![{\displaystyle p(n)=\sum _{i=0}^{n}p(2,i),\,n\,\geq \,0,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/2fbda537661b936d3592794cb788dd025342cfa6)
or
![{\displaystyle p(n)=1+\sum _{i=1}^{n}p(2,i),\,n\,\geq \,0.\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/69760d0c5562e724fee838b00fd0f9097cb053dc)
Partition function finite formulas
Emory University mathematicians Ken Ono and Zachary Kent, together with Amanda Folsom of Yale, have discovered that partition numbers behave like fractals. Ono and Jan Hendrik Bruinier, of the Technical University of Darmstadt, have devised the first finite formula to calculate the partitions of any number.[2][3]
The partition function can be expressed as a sum over the
pentagonal partitions of
. Let
n = k1 + 2 k2 + 5 k5 + ⋯ = qm kqm |
be a pentagonal partition of
, where each
is a
generalized pentagonal number (GPN), sequence
A001318, with
being the largest GPN less than or equal to
. Then
[4]
![{\displaystyle p(n)=\sum _{k_{1}=0}^{n}\sum _{k_{2}=0}^{\lfloor n/2\rfloor }\sum _{k_{5}=0}^{\lfloor n/5\rfloor }\cdots \sum _{k_{q_{M}}=0}^{\lfloor n/q_{M}\rfloor }(-1)^{A}\left({\begin{array}{c}K\\k_{1},k_{2},k_{5},\ldots ,k_{q_{M}}\end{array}}\right)\delta _{n,\sum q_{m}\,k_{q_{m}}},}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/001694a8a5d225f423781cfd8f4c220bde707763)
where
![{\displaystyle {\begin{aligned}K&=k_{1}+k_{2}+k_{5}+k_{7}+\cdots ,\\A&=k_{5}+k_{7}+k_{22}+k_{26}+\cdots =\sum _{m=\pm 2,\pm 4,\ldots }k_{q_{m}},\end{aligned}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/8f9f5459ae493988d327047cccdc0ec051e82205)
and where
-
![{\displaystyle \left({\begin{array}{c}K\\k_{1},\ldots ,k_{n}\end{array}}\right)\equiv {\frac {K!}{k_{1}!\cdots k_{n}!}}~\delta _{K,k_{1}+\cdots +k_{n}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/000e864349993d5f70fd9c410cb7a8ffe44961af)
is a
multinomial coefficient. The number of terms in the sum for
is sequence
A095699, e.g.
, and
-
![{\displaystyle {\begin{aligned}p(8)&=-\left({\begin{array}{c}2\\1,0,0,1\end{array}}\right)-\left({\begin{array}{c}3\\1,1,1,0\end{array}}\right)-\left({\begin{array}{c}4\\3,0,1,0\end{array}}\right)+\left({\begin{array}{c}4\\0,4,0,0\end{array}}\right)\\&~~~~\,+\left({\begin{array}{c}5\\2,3,0,0\end{array}}\right)+\left({\begin{array}{c}6\\4,2,0,0\end{array}}\right)+\left({\begin{array}{c}7\\6,1,0,0\end{array}}\right)+\left({\begin{array}{c}8\\8,0,0,0\end{array}}\right)\\&=-2-6-4+1+10+15+7+1=22.\end{aligned}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/9323f04178428d9542b5e821d499e8558e66c8c7)
Determinant formulas
The value of the partition function
can be found from
-
![{\displaystyle {\begin{matrix}{\text{GPN's}}&~\\{\begin{matrix}0\\1\\2\\~\\~\\5\\~\\7\\~\\\vdots \\\end{matrix}}&p(n)={\begin{vmatrix}~1&-1&~\\~1&~1&-1&~\\~0&~1&~1&-1&~\\~0&~0&~1&~1&-1&~\\-1&~0&~0&~1&~1&-1&~\\~0&-1&~0&~0&~1&~1&-1&~\\-1&~0&-1&~0&~0&~1&~1&-1&~\\~0&-1&~0&-1&~0&~0&~1&~1&-1&~\\~0&~0&-1&~0&-1&~0&~0&~1&~1&~\\~\vdots &~&~&~&~&~&~&~&~&\ddots \\\end{vmatrix}}_{n\times n}\end{matrix}}.}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/d0143fda6d9ecd46b7e7a5051912f278c34327c4)
is the determinant of the
truncation of the infinite-dimensional Toeplitz matrix shown above. The only non-zero diagonals of this matrix are those which start on a row labeled by a generalized pentagonal number
. (The superdiagonal is taken to start on row
0.) On these diagonals, the matrix element is
.
By using the identity by Ramanujan,[5]
![{\displaystyle \sum _{k=0}^{\infty }p(5k+4)\,x^{k}=5\,{\frac {(x^{5})_{\infty }^{5}}{(x)_{\infty }^{6}}},\,(x)_{\infty }\equiv \prod _{m=1}^{\infty }(1-x^{m}),}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/14e2491be6409fe7cc210a0639bb504678e8970b)
the partition function
can be expressed alternatively as the determinant of a lower,
-dimensional matrix:
![{\displaystyle p(5k-1)=5\,{\begin{vmatrix}~1&~&~&~&~&~&~&~1~\\-6&~1&~&~&~&~&~&~0~\\~9&-6&~1&~&~&~&~&~0~\\~10&~9&-6&~1&~&~&~&~0~\\-30&~10&~9&-6&~1&~&~&~0~\\~0&-30&~10&~9&-6&~1&~&-5~\\~11&~0&-30&~10&~9&-6&~&~0~\\~\vdots &~&~&~&~&~&\ddots &~\vdots ~\\\end{vmatrix}}_{k\times k}.}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/556016827d01d43a4111a9cf97e2f904aba5ba73)
The numbers making up the 1
st column correspond to sequence
A000729, while every 5
th element (after the initial
1) in the last column is from sequence
A000728:
{1, −5, 5, 10, −15, − 6, ...}
; all other elements in that column are zero. For example,
![{\displaystyle p(29)=5\,{\begin{vmatrix}~1&~&~&~&~&~1~\\-6&~1&~&~&~&~0~\\~9&-6&~1&~&~&~0~\\~10&~9&-6&~1&~&~0~\\-30&~10&~9&-6&~1&~0~\\0&-30&~10&~9&-6&-5~\\\end{vmatrix}}=4565.}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/59f590761e18d68fc3d2956ccb10a36ff6034fb8)
In a like fashion, by using two other identities by Ramanujan the partition functions
and
can also be expressed as
-dimensional determinants:
![{\displaystyle {\begin{aligned}p(7k-2)&=7\,{\begin{vmatrix}~1&~&~&~&1~\\-8&~1&~&~&3~\\~20&-8&~1&~&2~\\~0&~20&-8&~&8~\\~\vdots &~&~&\ddots &\vdots ~\\\end{vmatrix}}_{k\times k},\\p(25k-1)&=25\,{\begin{vmatrix}~1&~&~&~&63~\\-31&~1&~&~&4988~\\~434&-31&~1&~&95751~\\-3565&~434&-31&~&766014~\\~\vdots &~&~&\ddots &\vdots ~\\\end{vmatrix}}_{k\times k},\end{aligned}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/382c225bd6bb0d75df33f2cc1807bb8adc2af544)
where the first column in each matrix is sequence A000731 and A010836, respectively, and the last column in each is from the expansions:
![{\displaystyle {\begin{aligned}(x)_{\infty }^{4}(x^{7})_{\infty }^{3}+7x(x^{7})_{\infty }^{7}&=1+3x+2x^{2}+8x^{3}+\cdots ;\\&\\63(x)_{\infty }^{24}(x^{5})_{\infty }^{6}+5^{3}\cdot 52x(x)_{\infty }^{18}(x^{5})_{\infty }^{12}&+5^{5}\cdot 63x^{2}(x)_{\infty }^{12}(x^{5})_{\infty }^{18}\\+~5^{8}\cdot 6x^{3}(x)_{\infty }^{6}(x^{5})_{\infty }^{24}&+5^{10}\cdot x^{4}(x^{5})_{\infty }^{30}\\&=63+4988x+95751x^{2}+766014x^{3}+\cdots .\end{aligned}}}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/9b84ec6bfc701ae719d659d44eeb806b19a33b78)
As an example, the calculation of
is as follows:
-
![{\displaystyle p(149)=25\,{\begin{vmatrix}~1&~&~&~&~&~63~\\-31&~1&~&~&~&~4988~\\~434&-31&~1&~&~&~95751~\\-3565&~434&-31&~1&~&~766014~\\~18445&-3565&~434&-31&~1&~3323665~\\-57505&~18445&-3565&~434&-31&~8359848~\\\end{vmatrix}}=37027355200.}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/5580cc2abcc5d29b5dddd5ce0cf96c2b78cba712)
The partition function for partitions into
distinct integers,
, is
-
![{\displaystyle q(n)={\begin{vmatrix}~1&~&~&~&~&~&~&~&~1~\\-1&~1&~&~&~&~&~&~&~0~\\-1&-1&~1&~&~&~&~&~&-1~\\~0&-1&-1&~1&~&~&~&~&~0~\\~0&~0&-1&-1&~1&~&~&~&-1~\\~1&~0&~0&-1&-1&~1&~&~&~0~\\~0&~1&~0&~0&-1&-1&~1&~&~0~\\~1&~0&~1&~0&~0&-1&-1&~&~0~\\~\vdots &~&~&~&~&~&~&\ddots &~\vdots ~\\\end{vmatrix}}_{(n+1)\times (n+1)},}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/d2dfc28b4445beb326db42d409376497a450a085)
where the first column is sequence
A010815, and a matrix element in the last column equals
if the row number is
; otherwise it equals zero. By a result due to Euler,
is also the partition function for partitions into
odd integers.
First differences of the partition function
The first differences of the partition function are
![{\displaystyle p(n+1)-p(n)=p(2,n+1),\,n\geq 1,\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/efd54971f99cefdb484d49d4c9a4835965930eab)
where
is the number of partitions with parts of size 2 or larger.
Partial sums of the partition function
The n-th partial sum of the partition function is equal to the n X n deternminant
![{\displaystyle \sum _{k=0}^{n}p(k)={\begin{vmatrix}~2&-1&~\\~0&~2&-1&~\\-1&~0&~2&-1&~\\~0&-1&~0&~2&-1&~\\-1&~0&-1&~0&~2&-1&~\\~1&-1&~0&-1&~0&~2&-1&~\\~\vdots &~&~&~&~&~&\ddots &\ddots \\c_{n-1}&c_{n-2}&~&~&\cdots &~&~&~2&-1\\c_{n}&c_{n-1}&~&~&\cdots &~&~&~0&~2\end{vmatrix}}_{n\times n},}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/066a60526fc973bcdc0b1a04cb47327055b4d38e)
where c1 = 2, c2 = 0, and for k > 2,
![{\displaystyle c_{k}=\left\{{\begin{aligned}(-1)^{m+1}&&{\text{ if }}k=q_{m};\\(-1)^{m}&&{\text{ if }}k=q_{m}+1;\\0&&{\text{otherwise}}.\end{aligned}}\right.}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/f3c740f7380c4228b81a10698086bb7d9a1bb57d)
Partial sums of reciprocals of the partition function
The partials sums of reciprocals of the partition function are
![{\displaystyle \sum _{n=0}^{m}{\frac {1}{p(n)}}=~?\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/033705a9a85808cbd63cb7f73909cdc596eb8ba8)
Sum of reciprocals of the partition function
The sum of reciprocals of the partition function is
![{\displaystyle \sum _{n=0}^{\infty }{\frac {1}{p(n)}}=~?\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/104e54bf78470fe9cf3bba69560fd6338abbe353)
The decimal expansion is
(A078506)
Order of basis of representation of integers as sum of partition numbers
The order of basis of the representation of integers as sum of partition numbers is
![{\displaystyle ?\,}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/0d1a6a1a17548effda7086bf17c0a84917507bf1)
Sequences
A000041 Number of partitions of
.
-
{1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, ...}
A002865 Number of partitions
of
that do not contain
1 as a part. Corresponds to
.
-
{1, 0, 1, 1, 2, 2, 4, 4, 7, 8, 12, 14, 21, 24, 34, 41, 55, 66, 88, 105, 137, 165, 210, 253, 320, 383, 478, 574, 708, 847, 1039, 1238, 1507, 1794, 2167, 2573, 3094, 3660, 4378, 5170, 6153, 7245, 8591, ...}
A000070 Summatory function of the partition function,
.
-
{1, 2, 4, 7, 12, 19, 30, 45, 67, 97, 139, 195, 272, 373, 508, 684, 915, 1212, 1597, 2087, 2714, 3506, 4508, 5763, 7338, 9296, 11732, 14742, 18460, 23025, 28629, 35471, 43820, 53963, 66273, 81156, ...}
A078506 Decimal expansion of sum of inverses of unrestricted partition function.
-
{2, 5, 1, 0, 5, 9, 7, 4, 8, 3, 8, 8, 6, 2, 9, 3, 9, 5, 3, 2, 3, 6, 8, 3, 4, 7, 2, 7, 4, 1, 5, 4, 6, 5, 4, 5, 1, 6, 8, 3, 5, 3, 1, 9, 4, 4, 9, 5, 5, 1, 4, 7, 6, 8, 1, 9, 0, 8, 0, 6, 2, 9, 9, 6, 5, 0, 8, 3, 8, 4, 5, 3, 2, 9, 0, 4, 4, ...}
A190840 rounded to nearest integer.
-
{2, 3, 4, 6, 9, 13, 18, 26, 35, 48, 65, 87, 115, 152, 199, 258, 333, 427, 545, 692, 875, 1102, 1381, 1725, 2145, 2659, 3285, 4046, 4967, 6080, 7423, 9037, 10974, 13293, 16065, 19370, 23304, 27977, 33519, ...}
A035949. Number of partitions in parts not of the form
or
. Also number of partitions with no part of size
1 and differences between parts at distance
5 are greater than
1.
-
{0, 1, 1, 2, 2, 4, 4, 7, 8, 12, 14, 20, 23, 32, 39, 51, 61, 80, 95, 122, 146, 183, 219, 273, 324, 399, 475, 578, 685, 830, 979, 1177, 1387, 1655, 1945, 2311, 2705, 3198, 3737, 4396, 5121, 6003, 6973, 8143, 9439, ...}
See also
Notes
- ↑ George E. Andrews and Kimmo Eriksson, Integer partitions, Cambridge University Press (2004), p. 121.
- ↑ Carol Clark, New theories reveal the nature of numbers, Jan 20, 2011.
- ↑ Ken Ono, Hidden Structure to Partition Function (Mathematicians find a surprising fractal structure in number theory).
- ↑ J. Malenfant, “Finite, Closed-form Expressions for the Partition Function and for Euler, Bernoulli, and Stirling Numbers”.
- ↑ Berndt and Ono, “Ramanujan’s Unpublished Manuscript on the Partition and Tau Functions with Proofs and Commentary”.
External links
- M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
- Jan Hendrik Bruinier and Ken Ono, An Algebraic Formula for the Partition Function.
- Amanda Folsom, Zachary A. Kent, and Ken Ono, p-adic Properties of the Partition Function.
- Jerome Kelleher and Barry O’Sullivan, Generating All Partitions: A Comparison of Two Encodings, 2009.
- Peter Luschny, Counting with Partitions, 2009–02–20.
- Omar E. Pol, 3D image showing the partitions of 1 to 9.
- W. J. A. Colman, A General Method for Determining a Closed Formula for the Number of Partitions of the Integer n into m Positive Integers for Small Values of m, submitted May 1982.