This site is supported by donations to The OEIS Foundation.

Partition function

From OeisWiki

(Redirected from Number of partitions)
Jump to: navigation, search

This article needs more work.

Please help by expanding it!


The partition function \scriptstyle p(n) \, gives the number of partitions of a nonnegative integer \scriptstyle n \, 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.)

Contents

Table of partition function approximations

Note that \scriptstyle p(n) \,=\, F(n+1),\, 0 \,\le\, n \,\le\, 4 \,, where \scriptstyle F(n) \, is the \scriptstyle n \,th Fibonacci number. For the Hardy–Ramanujan asymptotic approximation, \scriptstyle [ \cdot ] \, is the nearest integer function.

Partition function approximations
\scriptstyle n \, \scriptstyle p(n) \,

\scriptstyle n \,\ge\, 0 \,


A000041

Hardy–Ramanujan

asymptotic

approximation \scriptstyle {\rm HR}(n) \,

\scriptstyle \left[ \tfrac{1}{4n \sqrt{3}} ~ \exp \left( \pi \sqrt{\tfrac{2n}{3}} \right) \right] \,


A190840\scriptstyle (n) \,

\scriptstyle n \,\ge\, 1 \,

\scriptstyle {\rm HR}(n) - p(n) \,

\scriptstyle n \,\ge\, 1 \,

A035949\scriptstyle (n-3) \,

\scriptstyle n \,\ge\, 4 \,

< 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 \scriptstyle p(n) \,, 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 \scriptstyle p(n) \,, 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 \scriptstyle p(n) \,? — 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
n \, p(n) \,


A000041

Differences

p(n) - \,

p(n-1) = \,

p(2, n), \,

n \,\ge\, 1 \,


A002865

Partial sums

\sum_{n=0}^{m} p(n) \,


A000070

Partial sums of reciprocals

\sum_{n=0}^{m} \frac{1}{p(n)} \,

< 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 \scriptstyle p(n)\, is the reciprocal of Euler's function

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)}.

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 \scriptstyle p(n)\, is given by

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}} \,

where \scriptstyle e^\pi \, is Gelfond's constant.

Partition function formula

The partition function \scriptstyle p(n) \,, is given by[1]

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}, \,

where \scriptstyle A_{k}(n) \, is an explicitly given finite sum of 24th roots of unity.

Note that \scriptstyle p(n) \,=\, 0 \, when \scriptstyle n \,<\, 0 \, since a negative integer is not the sum of positive integers, and \scriptstyle p(0) \,=\, 1 \, 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 \scriptstyle p(n) \,=\, 0 \, for \scriptstyle n \,<\, 0 \,) recursive formula for the partition function

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 \,

where \scriptstyle q_j \,=\, \frac{j(3j - 1)}{2},\, j \,\in\, \mathbb{Z}, \, are the generalized pentagonal numbers, with \scriptstyle j \, 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 \scriptstyle q_j \, (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 \scriptstyle j \,

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) \,

Intermediate partition function

The number of partitions of \scriptstyle n\, using only positive integers at least as large as \scriptstyle k \,, called the intermediate partition function \scriptstyle p(k, n) \,, is given by

p(k, n) = ?, \,

where \scriptstyle p(k, n) \,=\, 0 \, when \scriptstyle n \,<\, 0 \, or \scriptstyle k \,>\, n \,>\, 0, \, and \scriptstyle p(k, 0) \,=\, 1 \, since the empty partition gives the empty sum (the additive identity, 0).

Intermediate partition function formula

The intermediate partition function formula is

p(n) = 1 + \sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} p(i,n-i) \,

where we have the empty sum (the additive identity, 0) for the summation when \scriptstyle n \,<\, 2 \,, thus giving \scriptstyle p(n) \,=\, 1,\ 0 \,\le\, n \,\le\, 1 \,.

Intermediate partition function formula (other version)

The partition function may be expressed in terms of the intermediate partition function trivially as

p(n) = p(1, n),\, n \,\ge\, 0, \,

and since every partition of \scriptstyle n \, with smallest part 1 is trivially obtained from the partition of \scriptstyle n-1 \, without that part 1, we have

p(0) = 1,\, p(n) = p(n-1) + p(2, n),\, n \,\ge\, 1, \,

and by recursion we get

p(0) = 1,\, p(n) = [p(n-2) + p(2, n-1)] + p(2, n),\, n \,\ge\, 1, \,

...

p(0) = 1,\, p(n) = [p(n-3) + p(2, n-2)] + p(2, n-1) + p(2, n),\, n \,\ge\, 1, \,

...

p(0) = 1,\, p(n) = p(0) + \sum_{i=1}^{n} p(2, i),\, n \,\ge\, 1, \,

which may be rewritten as (where \scriptstyle p(k, 0) \,=\, 1 \, since the empty partition gives the empty sum, i.e. the additive identity, 0)

p(n) = \sum_{i=0}^{n} p(2, i),\, n \,\ge\, 0, \,

or

p(n) = 1 + \sum_{i=1}^{n} p(2, i),\, n \,\ge\, 0. \,

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 = k1 + 2k2 + 5k5 + . . . = \scriptstyle \sum_m q m kqm be a pentagonal partition of n, where each qm = m(3m-1)/2 is a generalized pentagonal number (GPN), sequence A001318, with qM being the largest GPN less than or equal to n. Then[4]

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}}},

where

\begin{align} 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{align}

and where

\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}

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

\begin{align} 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{align}

Determinant formulas

The value of the partition function p(n) can be found from

\begin{matrix} {\rm GPN's} \\ 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} .

p(n) is the determinant of the n X n 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 qm. (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]

\sum_{k=0}^{\infty} p(5k+4)x^k = 5~ \frac{ (x^5)^5_{\infty} } {(x)^6_{\infty}} , ~ (x)_{\infty} \equiv \prod_{m=1}^{\infty}(1-x^m),

the partition function p(5k-1) can be expressed alternatively as the determinant of a lower, k-dimensional matrix:

p(5k-1) = 5 \cdot\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} .

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,

p(29) = 5 \cdot\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.

In a like fashion, by using two other identities by Ramanujan the partition functions p(7k-2) and p(25k-1) can also be expressed as k-dimensional determinants:

\begin{align} p(7k-2) & = 7 \cdot\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 \cdot\begin{vmatrix} ~1& ~ &~& ~&63~\\ -31& ~1& ~ &~&4988~\\ ~434 & -31& ~1& ~ & 95751~\\ -3565 & ~434 & -31 & ~ & 766014~\\ ~ \vdots & ~&~& \ddots & \vdots~ \end{vmatrix}_{ k \times k } , \end{align}

where the first column in each matrix is sequence A000731 and A010836, respectively, and the last column in each is from the expansions:

\begin{align} (x)^4_{\infty} (x^7)^3_{\infty} +7x(x^7)^7_{\infty} &= 1 +3x+2x^2+8x^3 + \cdots ;\\& \\ 63 (x)^{24}_{\infty} (x^5)^{6}_{\infty} + 5^3 \cdot 52x (x)^{18}_{\infty} (x^5)^{12}_{\infty} &+ 5^5 \cdot 63x^2 (x)^{12}_{\infty} (x^5)^{18}_{\infty} \\ +~ 5^{8} \cdot 6x^3 (x)^{6}_{\infty} (x^5)^{24}_{\infty} &+ 5^{10} \cdot x^4 (x^5)^{30}_{\infty} \\ & = 63+4988x +95751x^2 +766014x^3 + \cdots. \end{align}

As an example, the calculation of p(149) is as follows:

p(149) = 25 \cdot \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 .


The partition function for partitions into distinct integers, q(n), is

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)} ,

where the first column is sequence A010815, and a matrix element in the last column equals (-1) m if the row number is 2qm+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

p(n+1) - p(n) = p(2, n+1),\, n \ge 1, \,

where \scriptstyle p(2, n+1) \, 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

\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} ,

where c1 = 2, c2 = 0, and for k > 2,

c_k = \left\{ \begin{align} (-1)^{m+1} ~ & {\rm if} ~k = q_m; \\ (-1)^m~~~ & {\rm if}~ k =q_m+1; \\ 0 ~~~~~ ~~ & {\rm otherwise}. \end{align} \right.

Partial sums of reciprocals of the partition function

The partials sums of reciprocals of the partition function are

\sum_{n=0}^{m} \frac{1}{p(n)} = ~? \,

Sum of reciprocals of the partition function

The sum of reciprocals of the partition function is

\sum_{n=0}^{\infty} \frac{1}{p(n)} = ~? \,

The decimal expansion is \scriptstyle 2.510597483886 \dots \, (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 \scriptstyle p(n) \, of \scriptstyle n,\ n \,\ge\, 0,\, (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 \scriptstyle p(2, n) \, of \scriptstyle n,\ n \,\ge\, 0,\, 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 \scriptstyle p(n) - p(n-1),\, n \,\ge\, 0. \,

The summatory function of the partition function, \scriptstyle \sum_{k=0}^{n} p(k), (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, ...}

\scriptstyle \tfrac{1}{4n \sqrt{3}} ~ \exp\big(\pi \sqrt{\tfrac{2n}{3}}\big) \, 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 \scriptstyle 13k,\, 13k+1 {\rm ~or~} 13k-1 \,. Also number of partitions with no part of size 1 and differences between parts at distance 5 are greater than 1. (A035949\scriptstyle (n),\, n \,\ge\, 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

  1. ↑ George E. Andrews and Kimmo Eriksson, Integer partitions, Cambridge University Press (2004), p. 121.
  2. ↑ Carol Clark, New theories reveal the nature of numbers, Jan 20, 2011.
  3. ↑ Ken Ono, Hidden Structure to Partition Function (Mathematicians find a surprising fractal structure in number theory).
  4. ↑ J. Malenfant, "Finite, Closed-form Expressions for the Partition Function and for Euler, Bernoulli, and Stirling Numbers".
  5. ↑ Berndt and Ono, "Ramanujan's Unpublished Manuscript on the Partition and Tau Functions with Proofs and Commentary". [1]

External links

Retrieved from "http://oeis.org/wiki/Partition_function"
Personal tools