This site is supported by donations to The OEIS Foundation.
Partition function
From OeisWiki
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 , where is the ^{th} Fibonacci number. For the Hardy–Ramanujan asymptotic approximation, is the nearest integer function.
 Hardy–Ramanujan
asymptotic approximation

 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 HardyRamanujan 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 HardyRamanujan (Modified) HardyRamanujan / 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
Differences
 Partial sums
 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
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
where is Gelfond's constant.
Partition function formula
The partition function , is given by^{[1]}
where is an explicitly given finite sum of 24^{th} 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
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
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
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
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
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
...
...
which may be rewritten as (where since the empty partition gives the empty sum, i.e. the additive identity, 0)
or
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 n. Let n = k_{1} + 2k_{2} + 5k_{5} + . . . = q _{m} k_{qm} be a pentagonal partition of n, where each q_{m} = m(3m1)/2 is a generalized pentagonal number (GPN), sequence A001318, with q_{M} being the largest GPN less than or equal to n. Then^{[4]}
where
and where
is a multinomial coefficient. The number of terms in the sum for p(n) is sequence A095699. E.g., 8=7+1 = 5+2+1 = 5+1+1+1 = 2+2+2+2 = . . . . , and
Determinant formulas
The value of the partition function p(n) can be found from
p(n) is the determinant of the n X n truncation of the infinitedimensional Toeplitz matrix shown above. The only nonzero diagonals of this matrix are those which start on a row labeled by a generalized pentagonal number q_{m}. (The superdiagonal is taken to start on row "0".) On these diagonals, the matrix element is (1)^{m+1}.
By using the identity by Ramanujan,^{[5]}
the partition function p(5k1) can be expressed alternatively as the determinant of a lower, kdimensional matrix:
The numbers making up the 1st column correspond to sequence A000729, while every 5th 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,
In a like fashion, by using two other identities by Ramanujan the partition functions p(7k2) and p(25k1) can also be expressed as kdimensional determinants:
where the first column in each matrix is sequence A000731 and A010836, respectively, and the last column in each is from the expansions:
As an example, the calculation of p(149) is as follows:
The partition function for partitions into distinct integers, q(n), is
where the first column is sequence A010815, and a matrix element in the last column equals (1)^{ m } if the row number is 2q_{m}+1; otherwise it equals zero. By a result due to Euler, q(n) is also the partition function for partitions into odd integers.
First differences of the partition function
The first differences of the partition function are
where is the number of partitions with parts of size 2 or larger.
Partial sums of the partition function
The nth partial sum of the partition function is equal to the n X n deternminant
where c_{1} = 2, c_{2} = 0, and for k > 2,
Partial sums of reciprocals of the partition function
The partials sums of reciprocals of the partition function are
Sum of reciprocals of the partition function
The sum of reciprocals of the partition function is
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
Sequences
The number of partitions of (A000041) are
 {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, ...}
The number of partitions of that do not contain 1 as a part (A002865) are
 {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, ...}
and correspond to
The summatory function of the partition function, , (A000070) gives
 {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, ...}
Decimal expansion of sum of inverses of unrestricted partition function. (Cf. A078506)
 {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, ...}
rounded to nearest integer. (A190840)
 {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, ...}
Number of partitions in parts not of the form . Also number of partitions with no part of size 1 and differences between parts at distance 5 are greater than 1. (A035949)
 {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, Closedform 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". [1]
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, pADIC 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, 20090220.
 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.