Partition function (number theory)
No closed-form expression for the partition function is known, but it has both asymptotic expansions that accurately approximate it and recurrence relations by which it can be calculated exactly.
It grows as an exponential function of the square root of its argument.
For instance, whenever the decimal representation of n ends in the digit 4 or 9, the number of partitions of n will be divisible by 5.
The equality between the products on the first and second lines of this formula is obtained by expanding each factor
(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
of positive integers can be found by taking only those terms in the first product for which
[3] 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.
The same sequence of pentagonal numbers appears in a recurrence relation for the partition function:[4]
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
In the 1960s, A. O. L. Atkin of the University of Illinois at Chicago discovered additional congruences of this form for small prime moduli.
Ken Ono (2000) proved that there are such congruences for every prime modulus greater than 3.
Later, Ahlgren & Ono (2001) showed there are partition congruences modulo every integer coprime to 6.
, reasonably close to the exact answer given above (1.415% larger than the true value).
Hardy and Ramanujan obtained an asymptotic expansion with this approximation as the first term:[13]
[13] In 1937, Hans Rademacher was able to improve on Hardy and Ramanujan's results by providing a convergent series expression for
The proof of Rademacher's formula involves Ford circles, Farey sequences, modular symmetry and the Dedekind eta function.
Paul Erdős (1942) published an elementary proof of the asymptotic formula for
[16][17] Techniques for implementing the Hardy–Ramanujan–Rademacher formula efficiently on a computer are discussed by Johansson (2012), who shows that
[18] The largest value of the partition function computed exactly is
[20] The generating function for the numbers q(n) is given by a simple infinite product:[21]
From this formula, one may easily obtain the first few terms (sequence A000009 in the OEIS):
Following identity is valid for the Pochhammer products: From this identity follows that formula: Therefore those two formulas are valid for the synthesis of the number sequence p(n): In the following, two examples are accurately executed: More generally, it is possible to consider partitions restricted to only elements of a subset A of the natural numbers (for example a restriction on the maximum value of the parts), or with a restriction on the number of parts or the maximum difference between parts.
Each particular restriction gives rise to an associated partition function with specific properties.
This is generalized as Glaisher's theorem, which states that the number of partitions with no more than d-1 repetitions of any part is equal to the number of partitions with no part divisible by d. If we denote
is the following Gaussian binomial coefficient: Some general results on the asymptotic properties of restricted partition functions are known.
If pA(n) is the partition function of partitions restricted to only elements of a subset A of the natural numbers, then: If A possesses positive natural density α then
and conversely if this asymptotic property holds for pA(n) then A has natural density α.
