, 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 theinteger as a sum ofpositive integers, where the order ofaddends 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

			(1)
			(2)
			(3)
			(4)
			(5)

it follows that. is sometimes called the number of unrestricted partitions, and is implemented in theWolfram Language asPartitionsP[n].

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

The first few prime values of are 2, 3, 5, 7, 11, 101, 17977, 10619863, ... (OEISA049575), corresponding to indices 2, 3, 4, 5, 6, 13, 36, 77, 132, ... (OEISA046063). As of Feb. 3, 2017, the largest known giving aprobable 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;http://primes.utm.edu/top20/page.php?id=54#records).

When explicitly listing the partitions of a number, the simplest form is the so-callednatural representation which simply gives the sequence of numbers in the representation (e.g., (2, 1, 1) for the number). Themultiplicity representation instead gives the number of times each number occurs together with that number (e.g., (2, 1), (1, 2) for). TheFerrers diagram is a pictorial representation of a partition. For example, the diagram above illustrates theFerrers diagram of the partition.

Euler gave agenerating function for using theq-series

			(6)
			(7)
			(8)

Here, the exponents are generalizedpentagonal numbers 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, ... (OEISA001318) and the sign of theth term (counting 0 as the 0th term) is (with thefloor function). Then the partition numbers are given by thegenerating function

			(9)
			(10)

(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 aFerrers 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 theEuler transform is the number of partitions of into integer parts.

Euler invented agenerating function which gives rise to arecurrence equation in,

(11)

(Skiena 1990, p. 57). Otherrecurrence equationsinclude

(12)

and

(13)

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

(14)

where is thefloor function and is theceiling function.

Arecurrence relation involving thepartitionfunction Q is given by

(15)

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

			(16)
			(17)
			(18)
			(19)

(Hirschhorn 1999).

MacMahon obtained the beautifulrecurrence relation

(20)

where the sum is over generalizedpentagonal numbers and the sign of theth term is, as above. Ramanujan stated without proof the remarkable identities

(21)

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

(22)

(Mordell 1922; Hardy 1999, pp. 89-90, typo corrected).

Hardy and Ramanujan (1918) used thecircle method andmodular functions to obtain the asymptotic solution

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

(24)

where

(25)

is theKronecker delta, and is thefloor function (Hardy 1999, pp. 120-121). The remainder after terms is

(26)

where and are fixed constants (Apostol 1997, pp. 104-110; Hardy 1999, pp. 121 and 128). Rather amazingly, thecontour used by Rademacher involvesFarey sequences andFord 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 as a finite sum of algebraic numbers as follows. Define the weight-2 meromorphic modular form by

(27)

were, is anEisenstein series, and is aDedekind eta function. Now define

(28)

where. Additionally let be any set of representatives of the equivalence classes of the integral binary quadratic form such that with and, and for each, let be the so-called CM point in theupper half-plane, for which. Then

(29)

where the trace is defined as

(30)

Ramanujan found numerouspartitionfunction P congruences.

Let be thegenerating function for the number of partitions of containingodd numbers only and be thegenerating function for the number of partitions of without duplication, then

			(31)
			(32)
			(33)
			(34)
			(35)
			(36)

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, ... (OEISA000009). The identity

(37)

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

Thegenerating 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

			(38)
			(39)

where

(40)

Let be the number of partitions ofeven numbers only, and let () be the number of partitions in which the parts are alleven (odd) and all different. Then thegenerating function of is given by

			(41)
			(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, ... (OEISA000700). Additionalgenerating 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

			(43)
			(44)
			(45)
			(46)

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

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

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

			(49)
			(50)
			(51)
			(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, ... (OEISA089958; Honsberger 1985, pp. 241-242).

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

			(53)
			(54)
			(55)
			(56)
			(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, ... (OEISA007690; Honsberger 1985, p. 241, correcting the sign error in equation57).

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

1. The number of partitions of in which noeven 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 iscongruent 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 iscongruent to 1 or 5 mod 6.

5. The number of partitions in which the parts are alleven and different is equal to the absolute difference of the number of partitions withodd andeven parts.

satisfies the inequality

(58)

(Honsberger 1991).

denotes the number of ways of writing as a sum ofexactly terms or, equivalently, the number of partitions into parts of which the largest isexactly. (Note that if "exactly" is changed to "or fewer" and "largest isexactly," is changed to "no elementgreater than," then thepartition functionq is obtained.) 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 theWolfram Language usingIntegerPartitions[n,k].

can be computed from therecurrence relation

(59)

(Skiena 1990, p. 58; Ruskey) with for,, and. The triangle of is given by

(60)

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

Therecurrence relation can be solved exactlyto give

			(61)
			(62)
			(63)
			(64)

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

			(65)
			(66)

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

(67)

and then yields

			(68)
			(69)
			(70)

Hardy and Ramanujan (1918) obtained the exact asymptotic formula

(71)

where is a constant. However, the sum

(72)

diverges, as first shown by Lehmer (1937).

See also

Related Wolfram sites

Explore with Wolfram|Alpha

More things to try:

• partitions
• prime number sequences
• asymptotes (2x^3 + 4x^2 - 9)/(3 - x^2)

References

MacMahon, P. A. "The Parity of, the Number of Partitions of, when."J. London Math. Soc.1, 225-226, 1926.

Rademacher, H. "On the Partition Function."Proc. London Math. Soc.43, 241-254, 1937.

Referenced on Wolfram|Alpha

Cite this as:

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

Subject classifications