Partition Function P

The partition function , sometimes also denoted (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 a nonnegative integer 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

it follows that . is sometimes called the number of unrestricted partitions, and is implemented in the Wolfram Language as PartitionsP[n]. The conventions are for the empty partition and for negative integers .

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

The first few prime values of 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 giving a probable prime is with decimal digits (E. Weisstein, Feb. 12, 2017), while the largest known giving a proven prime is with decimal digits (S. Batalov, Apr. 20, 2017; https://t5k.org/top20/page.php?id=54#records).

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

Similarly, all partitions of 8 are illustrated above in compact column form, with each column representing one partition and the horizontal subdivisions giving its parts.

Euler gave a generating function for using the q-series, for ,

Here, the exponents are generalized pentagonal numbers 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, ... (OEIS A001318) and the sign of the th term (counting 0 as the 0th term) is (with the floor function). Then the partition numbers are given by the generating function

(Hirschhorn 1999).

The number of partitions of a number into parts is equal to the number of partitions into parts of which the largest is , and the number of partitions into at most parts is equal to the number of partitions into parts which do not exceed . 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 for all , then the Euler transform is the number of partitions of into integer parts.

For , Euler's generating function gives rise to a recurrence equation in ,

(Skiena 1990, p. 57). Other recurrence equations include, for ,

and

for , where is the divisor function (Skiena 1990, p. 77; Berndt 1994, p. 108). For , there is also the identity

where is the floor function and is the ceiling function.

For , a recurrence relation involving the partition function Q is given by

Atkin and Swinnerton-Dyer (1954) obtained the following coefficientwise congruences

(Hirschhorn 1999).

MacMahon obtained the recurrence relation

for , where the sum is over generalized pentagonal numbers and the sign of the th term is , as above. Ramanujan stated without proof the remarkable identities

(Darling 1921; Mordell 1922; Hardy 1999, pp. 89-90), and

(Mordell 1922; Hardy 1999, pp. 89-90, typo corrected). Here, is a q-Pochhammer symbol for positive integer .

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

(Hardy 1999, p. 116), which was also independently discovered by Uspensky (1920). Rademacher (1937) subsequently obtained an exact convergent series solution whose first term has the Hardy-Ramanujan leading asymptotic behavior. For , it is given by

where

is the Kronecker delta, and is the floor function (Hardy 1999, pp. 120-121). For integers and , the remainder after terms satisfies

where and are fixed constants and (Apostol 1997, pp. 104-110; Hardy 1999, pp. 121 and 128; Johansson 2012, eq. (1.8)). 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) expressed , for positive integers , as a finite sum of algebraic numbers. Define the weight- modular form , which is a meromorphic function, by

where with , is an Eisenstein series, and is the Dedekind eta function. Now define

Let contain one representative of each -equivalence class of integral binary quadratic forms that are positive definite quadratic forms with discriminant , , , and . Here is the subgroup of the modular group Gamma represented by integer matrices whose lower-left entry is divisible by 6. For each , let be the CM point in the upper half-plane satisfying . Then

where the trace is defined as

Ramanujan found numerous partition function P congruences.

Let be the generating function for the number of partitions of containing odd numbers only and be the generating function for the number of partitions of without duplication, then, for ,

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

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

where

Let be the number of partitions of into even parts, and let () be the number of partitions of in which the parts are all even (odd) and all different. Then the generating function of is given by

(Hardy 1999, p. 86), and the first few values of for , 1, ... 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 of 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. Denote this common number by . Its generating function is

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

In general, let count the partitions of in which no part occurs more than times, where is a nonnegative integer. Its generating function is

(Honsberger 1985, pp. 241-242). Let count the partitions of in which every part occurs 2, 3, or 5 times. Its generating function is

The first few values of for , 1, ... are 1, 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).

Let count the partitions of in which no part occurs exactly once. Its generating function is

The first few values of for , 1, ... 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 36).

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

1. The number of partitions of in which no even part is repeated is the same as the number of partitions of 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 in which no part occurs more often than times is the same as the number of partitions in which no term is a multiple of .

3. The number of partitions of 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 in which no part appears exactly once is the same as the number of partitions of in which no part is congruent to 1 or 5 mod 6.

5. For each nonnegative integer , the number of partitions of into distinct odd parts is equal to the absolute difference between the numbers of partitions of into an even number of parts and into an odd number of parts (Kane 2018, Question 1).

satisfies the inequality

for (Honsberger 1991).

For nonnegative integers and , denotes the number of ways of writing as a sum of exactly positive integers or, equivalently, the number of partitions into parts of which the largest is exactly when . (Note that if "exactly " is changed to " or fewer" and "largest is exactly ," is changed to "no element greater than ," then the related function is obtained, as in the partition function Q.) For example, , since the partitions of 5 of length 3 are and , and the partitions of 5 with maximum element 3 are and .

The such partitions can be enumerated in the Wolfram Language using IntegerPartitions[n, k].

can be computed from the recurrence relation

for positive integers and with (Skiena 1990, p. 58; Ruskey). The boundary values are , for , and for or , with for . The number triangle of is given by

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

The recurrence relation can be solved exactly to give

for , with for . The functions can also be given explicitly for the first few values of in the simple forms

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

and then yields

Hardy and Ramanujan (1918) obtained the asymptotic formula

where is a fixed constant and the Hardy-Ramanujan terms are

Here is the coefficient in Rademacher's convergent series. However,

is a divergent series, as first shown by Lehmer (1937).