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:

Some exact values of p(n) for larger values of n include:^[1]

As of June 2022^[update], the largest known prime number among the values of p(n) is p(1289844341), with 40,000 decimal digits.^[2][3] Until March 2022, this was also the largest prime that has been proved using elliptic curve primality proving.^[4]

The generating function for p(n) is given by^[5]

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 ${\displaystyle x}$  in these lines are the pentagonal numbers ${\displaystyle P_{k}=k(3k-1)/2}$  for ${\displaystyle k\in \{0,1,-1,2,-2,\dots \}}$  (generalized somewhat from the usual pentagonal numbers, which come from the same formula for the positive values of ${\displaystyle k}$ ). The pattern of positive and negative signs in the third line comes from the term ${\displaystyle (-1)^{k}}$  in the fourth line: even choices of ${\displaystyle k}$  produce positive terms, and odd choices produce negative terms.

More generally, the generating function for the partitions of ${\displaystyle n}$  into numbers selected from a set ${\displaystyle A}$  of positive integers can be found by taking only those terms in the first product for which ${\displaystyle k\in A}$ . This result is due to Leonhard Euler.^[6] The formulation of Euler's generating function is a special case of a ${\displaystyle q}$ -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:^[7]

Another recurrence relation for ${\displaystyle p(n)}$  can be given in terms of the sum of divisors function σ:^[8]

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 ${\displaystyle n}$  ends in the digit 4 or 9, as expressed by the congruence^[10]

Ramanujan also discovered congruences modulo 7 and 11:^[10]

Since 5, 7, and 11 are consecutive primes, one might think that there would be an analogous congruence for the next prime 13, ${\displaystyle p(13k+a)\equiv 0{\pmod {13}}}$  for some a. However, there is no congruence of the form ${\displaystyle p(bk+a)\equiv 0{\pmod {b}}}$  for any prime b other than 5, 7, or 11.^[13] Instead, to obtain a congruence, the argument of ${\displaystyle p}$  should take the form ${\displaystyle cbk+a}$  for some ${\displaystyle c>1}$ . 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:

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.^[14][15]

Approximation formulas exist that are faster to calculate than the exact formula given above.

An asymptotic expression for p(n) is given by

${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)}$  as ${\displaystyle n\to \infty }$ .

This asymptotic formula was first obtained by G. H. Hardy and Ramanujan in 1918 and independently by J. V. Uspensky in 1920. Considering ${\displaystyle p(1000)}$ , the asymptotic formula gives about ${\displaystyle 2.4402\times 10^{31}}$ , 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:^[16]

The error after ${\displaystyle v}$  terms is of the order of the next term, and ${\displaystyle v}$  may be taken to be of the order of ${\displaystyle {\sqrt {n}}}$ . As an example, Hardy and Ramanujan showed that ${\displaystyle p(200)}$  is the nearest integer to the sum of the first ${\displaystyle v=5}$  terms of the series.^[16]

In 1937, Hans Rademacher was able to improve on Hardy and Ramanujan's results by providing a convergent series expression for ${\displaystyle p(n)}$ . It is^[17][18]

The proof of Rademacher's formula involves Ford circles, Farey sequences, modular symmetry and the Dedekind eta function.

It may be shown that the ${\displaystyle k}$ th term of Rademacher's series is of the order

Techniques for implementing the Hardy–Ramanujan–Rademacher formula efficiently on a computer are discussed by Johansson (2012), who shows that ${\displaystyle p(n)}$  can be computed in time ${\displaystyle O(n^{1/2+\varepsilon })}$  for any ${\displaystyle \varepsilon >0}$ . This is near-optimal in that it matches the number of digits of the result.^[21] The largest value of the partition function computed exactly is ${\displaystyle p(10^{20})}$ , which has slightly more than 11 billion digits.^[22]

Definition and properties edit

A partition in which no part occurs more than once is called strict, or is said to be a partition into distinct parts. The function q(n) gives the number of these strict partitions of the given sum n. For example, q(3) = 2 because the partitions 3 and 1 + 2 are strict, while the third partition 1 + 1 + 1 of 3 has repeated parts. The number q(n) is also equal to the number of partitions of n in which only odd summands are permitted.^[23]

Generating function edit

The generating function for the numbers q(n) is given by a simple infinite product:^[24]

Identities about strict partition numbers edit

Following identity is valid for the Pochhammer products:

${\displaystyle (x;x)_{\infty }^{-1}=(x^{2};x^{2})_{\infty }^{-1}(x;x^{2})_{\infty }^{-1}}$ 

From this identity follows that formula:

${\displaystyle {\biggl [}\sum _{n=0}^{\infty }p(n)x^{n}{\biggr ]}={\biggl [}\sum _{n=0}^{\infty }p(n)x^{2n}{\biggr ]}{\biggl [}\sum _{n=0}^{\infty }q(n)x^{n}{\biggr ]}}$ 

Therefore those two formulas are valid for the synthesis of the number sequence p(n):

${\displaystyle p(2n)=\sum _{k=0}^{n}p(n-k)q(2k)}$ 

${\displaystyle p(2n+1)=\sum _{k=0}^{n}p(n-k)q(2k+1)}$ 

In the following, two examples are accurately executed:

${\displaystyle p(8)=\sum _{k=0}^{4}p(4-k)q(2k)=}$ 

${\displaystyle =p(4)q(0)+p(3)q(2)+p(2)q(4)+p(1)q(6)+p(0)q(8)=}$ 

${\displaystyle =5\times 1+3\times 1+2\times 2+1\times 4+1\times 6=22}$ 

${\displaystyle p(9)=\sum _{k=0}^{4}p(4-k)q(2k+1)=}$ 

${\displaystyle =p(4)q(1)+p(3)q(3)+p(2)q(5)+p(1)q(7)+p(0)q(9)=}$ 

${\displaystyle =5\times 1+3\times 2+2\times 3+1\times 5+1\times 8=30}$ 

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. Some common examples are given below.

Euler and Glaisher's theorem edit

Two important examples are the partitions restricted to only odd integer parts or only even integer parts, with the corresponding partition functions often denoted ${\displaystyle p_{o}(n)}$  and ${\displaystyle p_{e}(n)}$ .

A theorem from Euler shows that the number of strict partitions is equal to the number of partitions with only odd parts: for all n, ${\displaystyle q(n)=p_{o}(n)}$ . 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.

Gaussian binomial coefficient edit

If we denote ${\displaystyle p(N,M,n)}$  the number of partitions of n in at most M parts, with each part smaller or equal to N, then the generating function of ${\displaystyle p(N,M,n)}$  is the following Gaussian binomial coefficient:

${\displaystyle \sum _{n=0}^{\infty }p(N,M,n)q^{n}={N+M \choose M}_{q}={\frac {(1-q^{N+M})(1-q^{N+M-1})\cdots (1-q^{N+1})}{(1-q)(1-q^{2})\cdots (1-q^{M})}}}$ 

Asymptotics edit

Some general results on the asymptotic properties of restricted partition functions are known. If p_A(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 ${\displaystyle \log p_{A}(n)\sim C{\sqrt {\alpha n}}}$ , with ${\displaystyle C=\pi {\sqrt {\frac {2}{3}}}}$ 

and conversely if this asymptotic property holds for p_A(n) then A has natural density α.^[25] This result was stated, with a sketch of proof, by Erdős in 1942.^[19][26]

If A is a finite set, this analysis does not apply (the density of a finite set is zero). If A has k elements whose greatest common divisor is 1, then^[27]

${\displaystyle p_{A}(n)=\left(\prod _{a\in A}a^{-1}\right)\cdot {\frac {n^{k-1}}{(k-1)!}}+O(n^{k-2}).}$ 

• First 4096 values of the partition function