The values of the partition function (1, 2, 3, 5, 7, 11, 15, and 22) can be determined by counting the Young diagrams for the partitions of the numbers from 1 to 8.
In number theory, the partition functionp(n) represents the number of possible partitions of a non-negative integer n. For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4.
For a positive integer n, p(n) is the number of distinct ways of representing n as a sum of positive integers. For the purposes of this definition, the order of the terms in the sum is irrelevant: two sums with the same terms in a different order are not considered to be distinct.
By convention p(0) = 1, as there is one way (the empty sum) of representing zero as a sum of positive integers. Furthermore p(n) = 0 when n is negative.
The first few values of the partition function, starting with p(0) = 1, are:
Using Euler's method to find p(40): A ruler with plus and minus signs (grey box) is slid downwards, the relevant terms added or subtracted. The positions of the signs are given by differences of alternating natural (blue) and odd (orange) numbers. In the SVG file, hover over the image to move the ruler.
The equality between the products on the first and second lines of this formula
is obtained by expanding each factor into the geometric series
To see that the expanded product equals the sum on the first line,
apply the distributive law to the product. This expands the product into a sum of monomials of the form for some sequence of coefficients
, only finitely many of which can be non-zero.
The exponent of the term is , and this sum can be interpreted as a representation of as a partition into copies of each number . Therefore, the number of terms of the product that have exponent is exactly , the same as the coefficient of in the sum on the left.
Therefore, the sum equals the product.
The function that appears in the denominator in the third and fourth lines of the formula is the Euler function. The equality between the product on the first line and the formulas in the third and fourth lines is Euler's pentagonal number theorem.
The exponents of in these lines are the pentagonal numbers for (generalized somewhat from the usual pentagonal numbers, which come from the same formula for the positive values of ). The pattern of positive and negative signs in the third line comes from the term in the fourth line: even choices of produce positive terms, and odd choices produce negative terms.
More generally, the generating function for the partitions of into numbers selected from a set of positive integers can be found by taking only those terms in the first product for which . This result is due to Leonhard Euler. The formulation of Euler's generating function is a special case of a -Pochhammer symbol and is similar to the product formulation of many modular forms, and specifically the Dedekind eta function.
As base cases, is taken to equal , and is taken to be zero for negative . Although the sum on the right side appears infinite, it has only finitely many nonzero terms,
coming from the nonzero values of in the range
Srinivasa Ramanujan is credited with discovering that the partition function has nontrivial patterns in modular arithmetic.
For instance the number of partitions is divisible by five whenever the decimal representation of ends in the digit 4 or 9, as expressed by the congruence
For instance, the number of partitions for the integer 4 is 5.
For the integer 9, the number of partitions is 30; for 14 there are 135 partitions. This congruence is implied by the more general identity
also by Ramanujan, where the notation denotes the product defined by
Since 5, 7, and 11 are consecutive primes, one might think that there would be an analogous congruence for the next prime 13, for some a. However, there is no congruence of the form for any prime b other than 5, 7, or 11. Instead, to obtain a congruence, the argument of should take the form for some . In the 1960s, A. O. L. Atkin of the University of Illinois at Chicago discovered additional congruences of this form for small prime moduli. For example:
This asymptotic formula was first obtained by G. H. Hardy and Ramanujan in 1918 and independently by J. V. Uspensky in 1920. Considering , the asymptotic formula gives about , reasonably close to the exact answer given above (1.415% larger than the true value).
The error after terms is of the order of the next term, and may be taken to be of the order of . As an example, Hardy and Ramanujan showed that is the nearest integer to the sum of the first terms of the series.
It may be shown that the th term of Rademacher's series is of the order
so that the first term gives the Hardy–Ramanujan asymptotic approximation.
Paul Erdős (1942) published an elementary proof of the asymptotic formula for .
Techniques for implementing the Hardy–Ramanujan–Rademacher formula efficiently on a computer are discussed by Johansson (2012), who shows that can be computed in time for any . This is near-optimal in that it matches the number of digits of the result. The largest value of the partition function computed exactly is , which has slightly more than 11 billion digits.
If no summand occurs repeatedly in the affected partition sums, then the so called strict partitions are present. The function Q(n) gives the number of these strict partitions in relation to the given sum n. Therefore the strict partition sequence Q(n) satisfies the criterion Q(n) ≤ P(n) for all . The same result results if only odd summands may appear in the partition sum, but these may also occur more than once.
Exemplary values of strict partition numbers
Representations of the partitions:
Exemplary values of Q(n) and associated number partitions