TOPICS
Search

Partition Function P


P(n), sometimes also denoted p(n) (Abramowitz and Stegun 1972, p. 825; Comtet 1974, p. 94; Hardy and Wright 1979, p. 273; Conway and Guy 1996, p. 94; Andrews 1998, p. 1), gives the number of ways of writing the integer n as a sum of positive integers, where the order of addends is not considered significant. By convention, partitions are usually ordered from largest to smallest (Skiena 1990, p. 51). For example, since 4 can be written

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

it follows that P(4)=5. P(n) is sometimes called the number of unrestricted partitions, and is implemented in the Wolfram Language as PartitionsP[n].

The values of P(n) for n=1, 2, ..., are 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ... (OEIS A000041). The values of P(10^n) for n=0, 1, ... are given by 1, 42, 190569292, 24061467864032622473692149727991, ... (OEIS A070177).

The first few prime values of P(n) are 2, 3, 5, 7, 11, 101, 17977, 10619863, ... (OEIS A049575), corresponding to indices 2, 3, 4, 5, 6, 13, 36, 77, 132, ... (OEIS A046063). As of Feb. 3, 2017, the largest known n giving a probable prime is 1000007396 with 35219 decimal digits (E. Weisstein, Feb. 12, 2017), while the largest known n giving a proven prime is 221444161 with 16569 decimal digits (S. Batalov, Apr. 20, 2017; http://primes.utm.edu/top20/page.php?id=54#records).

PartitionFerrersDiagram

When explicitly listing the partitions of a number n, the simplest form is the so-called natural representation which simply gives the sequence of numbers in the representation (e.g., (2, 1, 1) for the number 4=2+1+1). The multiplicity representation instead gives the number of times each number occurs together with that number (e.g., (2, 1), (1, 2) for 4=2·1+1·2). The Ferrers diagram is a pictorial representation of a partition. For example, the diagram above illustrates the Ferrers diagram of the partition 6+3+3+2+1=15.

Euler gave a generating function for P(n) using the q-series

(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)

Here, the exponents are generalized pentagonal numbers 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, ... (OEIS A001318) and the sign of the kth term (counting 0 as the 0th term) is (-1)^(|_(k+1)/2_|) (with |_x_| the floor function). Then the partition numbers P(n) are given by the generating function

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

(Hirschhorn 1999).

The number of partitions of a number n into m parts is equal to the number of partitions into parts of which the largest is m, and the number of partitions into at most m parts is equal to the number of partitions into parts which do not exceed m. Both these results follow immediately from noting that a Ferrers diagram can be read either row-wise or column-wise (although the default order is row-wise; Hardy 1999, p. 83).

For example, if a_n=1 for all n, then the Euler transform b_n is the number of partitions of n into integer parts.

Euler invented a generating function which gives rise to a recurrence equation in 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). Other recurrence equations include

 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)

and

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

where sigma_1(n) is the divisor function (Skiena 1990, p. 77; Berndt 1994, p. 108), as well as the identity

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

where |_x_| is the floor function and [x] is the ceiling function.

A recurrence relation involving the partition function Q is given by

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

Atkin and Swinnerton-Dyer (1954) obtained the unexpected identities

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 obtained the beautiful recurrence relation

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

where the sum is over generalized pentagonal numbers <=n and the sign of the kth term is (-1)^(|_(k+1)/2_|), as above. Ramanujan stated without proof the remarkable identities

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

 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, typo corrected).

Hardy and Ramanujan (1918) used the circle method and modular functions to obtain the asymptotic solution

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

(Hardy 1999, p. 116), which was also independently discovered by Uspensky (1920). Rademacher (1937) subsequently obtained an exact convergent series solution which yields the Hardy-Ramanujan formula (23) as the first term:

 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)

where

 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) is the Kronecker delta, and |_x_| is the floor function (Hardy 1999, pp. 120-121). The remainder after N terms is

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

where C and D are fixed constants (Apostol 1997, pp. 104-110; Hardy 1999, pp. 121 and 128). Rather amazingly, the contour used by Rademacher involves Farey sequences and Ford circles (Apostol 1997, pp. 102-104; Hardy 1999, pp. 121-122). In 1942, Erdős showed that the formula of Hardy and Ramanujan could be derived by elementary means (Hoffman 1998, p. 91).

Bruinier and Ono (2011) found an algebraic formula for the partition function P(n) as a finite sum of algebraic numbers as follows. Define the weight-2 meromorphic modular form F(z) by

 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)

were q=e^(2piiz), E_2(q) is an Eisenstein series, and eta(q) is a Dedekind eta function. Now define

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

where z=x+iy. Additionally let Q_n be any set of representatives of the equivalence classes of the integral binary quadratic form Q(x,y)=ax^2+bxy+cy^2 such that 6|a with a>0 and b=1 (mod 12), and for each Q(x,y), let alpha_Q be the so-called CM point in the upper half-plane, for which Q(alpha_Q,1)=0. Then

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

where the trace is defined as

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

Ramanujan found numerous partition function P congruences.

Let f_O(x) be the generating function for the number of partitions P_O(n) of n containing odd numbers only and f_D(x) be the generating function for the number of partitions P_D(n) of n without duplication, then

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)

as discovered by Euler (Honsberger 1985; Andrews 1998, p. 5; Hardy 1999, p. 86), giving the first few values of P_O(n)=P_D(n) for n=0, 1, ... as 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (OEIS A000009). The identity

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

is known as the Euler identity (Hardy 1999, p. 84).

The generating function for the difference between the number of partitions into an even number of unequal parts and the number of partitions in an odd number of unequal parts is given by

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)

where

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

Let P_E(n) be the number of partitions of even numbers only, and let P_(EO)(n) (P_(DO)(n)) be the number of partitions in which the parts are all even (odd) and all different. Then the generating function of P_(DO)(n) is given by

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

(Hardy 1999, p. 86), and the first few values of are 1, 1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, ... (OEIS A000700). Additional generating functions are given by Honsberger (1985, pp. 241-242).

Amazingly, the number of partitions with no even part repeated is the same as the number in which no part occurs more than three times and the same as the number in which no part is divisible by 4, all of which share the generating functions

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)

The first few values of P^*(n) are 1, 2, 3, 4, 6, 9, 12, 16, 22, 29, 38, ... (OEIS A001935; Honsberger 1985, pp. 241-242).

In general, the generating function for the number of partitions in which no part occurs more than d times is

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). The generating function for the number of partitions in which every part occurs 2, 3, or 5 times is

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)

The first few values are 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).

The number of partitions in which no part occurs exactly once is

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)

The first few values are, 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, correcting the sign error in equation 57).

Some additional interesting theorems following from these (Honsberger 1985, pp. 64-68 and 143-146) are:

1. The number of partitions of n in which no even part is repeated is the same as the number of partitions of n in which no part occurs more than three times and also the same as the number of partitions in which no part is divisible by four.

2. The number of partitions of n in which no part occurs more often than d times is the same as the number of partitions in which no term is a multiple of d+1.

3. The number of partitions of n in which each part appears either 2, 3, or 5 times is the same as the number of partitions in which each part is congruent mod 12 to either 2, 3, 6, 9, or 10.

4. The number of partitions of n in which no part appears exactly once is the same as the number of partitions of n in which no part is congruent to 1 or 5 mod 6.

5. The number of partitions in which the parts are all even and different is equal to the absolute difference of the number of partitions with odd and even parts.

P(n) satisfies the inequality

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

(Honsberger 1991).

P(n,k) denotes the number of ways of writing n as a sum of exactly k terms or, equivalently, the number of partitions into parts of which the largest is exactly k. (Note that if "exactly k" is changed to "k or fewer" and "largest is exactly k," is changed to "no element greater than k," then the partition function q is obtained.) For example, P(5,3)=2, since the partitions of 5 of length 3 are {3,1,1} and {2,2,1}, and the partitions of 5 with maximum element 3 are {3,2} and {3,1,1}.

The P(n,k) such partitions can be enumerated in the Wolfram Language using IntegerPartitions[n, {k}].

P(n,k) can be computed from the recurrence relation

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

(Skiena 1990, p. 58; Ruskey) with P(n,k)=0 for k>n, P(n,n)=1, and P(n,0)=0. The triangle of P(k,n) is given by

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

(OEIS A008284). The number of partitions of n with largest part k is the same as P(n,k).

The recurrence relation can be solved exactly to give

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)

where P(n,k)=0 for n<k. The functions P(n,k) can also be given explicitly for the first few values of k in the simple forms

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

where |_x_| is the floor function and [x] is the nearest integer function (Honsberger 1985, pp. 40-45). A similar treatment by B. Schwennicke defines

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

and then yields

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 and Ramanujan (1918) obtained the exact asymptotic formula

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

where alpha is a constant. However, the sum

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

diverges, as first shown by Lehmer (1937).


See also

Alcuin's Sequence, Conjugate Partition, Elder's Theorem, Euler Identity, Ferrers Diagram, Göllnitz's Theorem, Partition, Partition Function P Congruences, Partition Function q, Partition Function Q, Pentagonal Number, Pentagonal Number Theorem, Plane Partition, Random Partition, Rogers-Ramanujan Identities, Self-Conjugate Partition, Stanley's Theorem, Sum of Squares Function, Tau Function

Related Wolfram sites

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

Explore with Wolfram|Alpha

References

Abramowitz, M. and Stegun, I. A. (Eds.). "Unrestricted Partitions." §24.2.1 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. 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. The Theory of Partitions. Cambridge, England: Cambridge University Press, 1998.Apostol, T. M. Ch. 4 in Introduction to Analytic Number Theory. New York: Springer-Verlag, 1976.Apostol, T. M. "Rademacher's Series for the Partition Function." Ch. 5 in Modular Functions and Dirichlet Series in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 94-112, 1997.Atkin, A. O. L. and Swinnerton-Dyer, P. "Some Properties of Partitions." Proc. London Math. Soc. 4, 84-106, 1954.Berndt, B. C. Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, 1994.Bruinier, J. H. and Ono, K. "Algebraic Formulas for the Coefficients of Half-Integral Weight Harmonic Weak Maass Forms." http://arxiv.org/abs/1104.1182/. 6 Apr 2011.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, p. 307, 1974.Conway, J. H. and Guy, R. K. The Book of Numbers. 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.; and Barton, D. E. Symmetric Function and Allied Tables. 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.; and Miller, J. C. P. Royal Society Mathematical Tables, Vol. 4: Tables of Partitions. London: Cambridge University Press, 1958.Hardy, G. H. "Ramanujan's Work on Partitions" and "Asymptotic Theory of Partitions." Chs. 6 and 8 in Ramanujan: Twelve Lectures on Subjects Suggested by His Life and Work, 3rd ed. New York: Chelsea, pp. 83-100 and 113-131, 1999.Hardy, G. H. and Ramanujan, S. "Asymptotic Formulae in Combinatory Analysis." Proc. London Math. Soc. 17, 75-115, 1918.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. 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. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, 1998.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 40-45 and 64-68, 1985.Honsberger, R. More Mathematical Morsels. Washington, DC: Math. Assoc. Amer., pp. 237-239, 1991.Jackson, D. and Goulden, I. Combinatorial Enumeration. 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. Combinatory Analysis. 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. Implementing Discrete Mathematics: Combinatorics and Graph Theory with 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. and Plouffe, S. The Encyclopedia of Integer Sequences. 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.

Referenced on Wolfram|Alpha

Partition Function P

Cite this as:

Weisstein, Eric W. "Partition Function P." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PartitionFunctionP.html

Subject classifications