Partition Function P

$P(n)$ gives the number of ways of writing the Integer $n$ as a sum of Positive Integers without regard to order. For example, since 4 can be written

$$4 = 4$$

$$= 3+1$$

$$= 2+2$$

$$= 2+1+1$$

$$= 1+1+1+1,$$ (1)

so $P(4)=5$. $P(n)$ satisfies

$$P(n)\leq {\textstyle{1\over 2}}[P(n+1)+P(n-1)]$$ (2)

(Honsberger 1991). The values of $P(n)$ for $n=1$, 2, ..., are 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ... (Sloane's A000041). The following table gives the value of $P(n)$ for selected small $n$.

$n$	$P(n)$
50	204226
100	190569292
200	3972999029388
300	9253082936723602
400	6727090051741041926
500	2300165032574323995027
600	458004788008144308553622
700	60378285202834474611028659
800	5733052172321422504456911979
900	415873681190459054784114365430
1000	24061467864032622473692149727991

$n$ for which $P(n)$ is Prime are 2, 3, 4, 5, 6, 13, 36, 77, 132, 157, 168, 186, ... (Sloane's A046063). Numbers which cannot be written as a Product of $P(n)$ are 13, 17, 19, 23, 26, 29, 31, 34, 37, 38, 39, ... (Sloane's A046064), corresponding to numbers of nonisomorphic Abelian Groups which are not possible for any group order.

When explicitly listing the partitions of a number $n$, the simplest form is the so-called natural representation which simply gives the sequence of numbers in the representation (e.g., (2, 1, 1) for the number $4=2+1+1$). The multiplicity representation instead gives the number of times each number occurs together with that number (e.g., (2, 1), (1, 2) for $4=2\cdot 1+1\cdot 2$). The Ferrers Diagram is a pictorial representation of a partition.

Euler invented a Generating Function which gives rise to a Power Series in $P(n)$,

$$P(n)=\sum_{m=1}^\infty (-1)^{m+1} [P(n-{\textstyle{1\over 2}}m(3m-1))+P(n-{\textstyle{1\over 2}}m(3m+1))].$$ (3)

A Recurrence Relation is

$$P(n)={1\over n} \sum_{m=0}^{n-1} \sigma(n-m)P(m),$$ (4)

where $\sigma(n)$ is the Divisor Function (Berndt 1994, p. 108). Euler also showed that, for

$$f(x) \equiv \prod_{m=1}^\infty (1-x^m)=\sum_{n=-\infty}^\infty (-1)^nx^{n(3n+1)/2}$$ (5)

$$= 1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}+\ldots,$$ (6)

where the exponents are generalized Pentagonal Numbers 0, 1, 2, 5, 7, 12, 15, 22, 26, 35, ... (Sloane's A001318) and the sign of the $k$th term (counting 0 as the 0th term) is $(-1)^{\left\lfloor{(k+1)/2}\right\rfloor }$ (with $\left\lfloor{x}\right\rfloor$ the Floor Function), the partition numbers $P(n)$ are given by the Generating Function

$${1\over f(x)} = \sum_{n=0}^\infty P(n)x^n.$$ (7)

MacMahon obtained the beautiful Recurrence Relation

$$P(n)-P(n-1)-P(n-2)+P(n-5)+P(n-7)-P(n-12)-P(n-15)+\ldots = 0,$$ (8)

where the sum is over generalized Pentagonal Numbers $\leq n$ and the sign of the $k$th term is $(-1)^{\left\lfloor{(k+1)/2}\right\rfloor }$, as above.

In 1916-1917, Hardy and Ramanujan used the Circle Method and elliptic Modular Functions to obtain the approximate solution

$$P(n)\sim {1\over 4n\sqrt{3}} e^{\pi\sqrt{2n/3}}.$$ (9)

Rademacher (1937) subsequently obtained an exact series solution which yields the Hardy-Ramanujan Formula (9) as the first term:

$$P(n)=\sum_{q=1}^\infty L_q(n)\psi_q(n),$$ (10)

where

$$K = \pi \sqrt{2\over 3}$$ (11)

$$L_q(n) = \sum_p \omega_{p,q} e^{-2np\pi i/q}$$ (12)

$$\omega_{p,q} = e^{\pi i s_{p,q}}$$ (13)

$$s_{p,q} = {1\over q} \sum_{\mu=1}^{q-1} \mu\left({{\mu p\over q}-\left\lfloor{\mu p\over q}\right\rfloor -{1\over 2}}\right)$$ (14)

$$\lambda_n = \sqrt{n-{\textstyle{1\over 24}}}$$ (15)

$$\psi_q(n) = {\sqrt{q}\over\pi\sqrt{2}}\left\{{{d\over dm} \left[{\sinh\left({K\lambda_m\over q}\right)\over\lambda_m}\right]}\right\}_{m=n},$$ (16)

$\left\lfloor{x}\right\rfloor$ is the Floor Function, and $p$ runs through the Integers less than and Relatively Prime to $q$ (when $q=1$, $p=0$). The remainder after $Q$ terms is

$$R(Q)< CQ^{-1/2}+D\sqrt{Q\over n} \sinh\left({K\sqrt{n}\over Q}\right),$$ (17)

where $C$ and $D$ are fixed constants.

With $f(x)$ as defined above, Ramanujan also showed that

$$5 {f^5(x^5)\over f^6(x)} = \sum_{m=0}^\infty P(5m+4)x^m.$$ (18)

Ramanujan also found numerous Congruences such as

$$P(5m+4)\equiv 0\ \left({{\rm mod\ } {5}}\right)$$ (19)

$$P(7m+5)\equiv 0\ \left({{\rm mod\ } {7}}\right)$$ (20)

$$P(11m+6)\equiv 0\ \left({{\rm mod\ } {11}}\right).$$ (21)

Ramanujan's Identity gives the first of these.

Let $P_O(n)$ be the number of partitions of $n$ containing Odd numbers only and $P_D(n)$ be the number of partitions of $n$ without duplication, then

$P_O(n)=P_D(n)=\prod_{k=1,3,\dots}^\infty (1+x^k+x^{2k}+x^{3k}+\ldots)$
$= \prod_{k=1}^\infty(1+x^k)=1+x+x^2+2x^3+2x^4+3x^5+\ldots,\quad$	(22)

as discovered by Euler (Honsberger 1985). The first few values of $P_O=P_D$ are 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (Sloane's A000009).

Let $P_E(n)$ be the number of partitions of Even numbers only, and let $P_{EO}(n)$ ($P_{DO}(n)$) be the number of partitions in which the parts are all Even (Odd) and all different. The first few values of $P_{DO}(n)$ are 1, 1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, ... (Sloane's A000700). Some additional Generating Functions are given by Honsberger (1985, pp. 241-242)

$\sum_{n=1}^\infty P_{\rm no\ even\ part\ repeated}(n)x^n=\prod_{k=1} (1-x^{2k-1})^{-1}(1+x^{2k})$	(23)
$\sum_{n=1}^\infty P_{\rm no\ part\ occurs\ more\ than\ 3\ times}(n)x^n = \prod_{k=1} (1+x^k+x^{2k}+x^{3k})$	(24)
$\sum_{n=1}^\infty P_{\rm no\ part\ divisible\ by\ 4}(n)x^n =\prod_{k=1} {1-x^{4k}\over 1-x^k}$	(25)
$\sum_{n=1}^\infty P_{\rm no\ part\ occurs\ more\ than\ {\it d}\ times}(n)x^n=\prod_{k=1} \sum_{i=0}^d x^{ik} = \prod_{k=1} {1-x^{(d+1)k}\over 1-x^k}$	(26)
$\sum_{n=1}^\infty P_{\rm every\ part\ occurs\ 2,\ 3,\ or\ 5\ times}(n)x^n=\prod_{k=1} (1+x^{2k}+x^{3k}+x^{5k})$
$= \prod_{k=1} (1+x^{2k})(1+x^{3k}) = \prod_{k=1} {1-x^{4k}\over 1-x^{2k}} {1-x^{6k}\over 1-x^{3k}}$	(27)
$\sum_{n=1}^\infty P_{\rm no\ part\ occurs\ exactly\ once}(n)x^n = (1+x^{2k}+x^{3k}+\ldots)=\prod_k {1+x^{6k}\over (1-x^{2k})(1-x^{3k})}.$	(28)

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

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

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

5. The number of partitions in which the parts are all Even and different is equal to the absolute difference of the number of partitions with Odd and Even parts.

$P(n,k)$, also written $P_k(n)$, is the number of ways of writing $n$ as a sum of $k$ terms, and can be computed from the Recurrence Relation

$$P(n,k)=P(n-1,k-1)+P(n-k,k)$$ (29)

(Ruskey). The number of partitions of $n$ with largest part $k$ is the same as $P(n,k)$.

The function $P(n,k)$ can be given explicitly for the first few values of $k$,

$$P(n,2) = \left\lfloor{{\textstyle{1\over 2}}n}\right\rfloor$$ (30)

$$P(n,3) = [{\textstyle{1\over 12}} n^2],$$ (31)

where $\left\lfloor{x}\right\rfloor$ is the Floor Function and $[x]$ is the Nint function (Honsberger 1985, pp. 40-45).

See also Alcuin's Sequence, Elder's Theorem, Euler's Pentagonal Number Theorem, Ferrers Diagram, Partition Function Q, Pentagonal Number, r(n), Rogers-Ramanujan Identities, Stanley's Theorem

References

Abramowitz, M. and Stegun, C. A. (Eds.). ``Unrestricted Partitions.'' §24.2.1 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 825, 1972.

Adler, H. ``Partition Identities--From Euler to the Present.'' Amer. Math. Monthly 76, 733-746, 1969.

Adler, H. ``The Use of Generating Functions to Discover and Prove Partition Identities.'' Two-Year College Math. J. 10, 318-329, 1979.

Andrews, G. Encyclopedia of Mathematics and Its Applications, Vol. 2: The Theory of Partitions. Cambridge, England: Cambridge University Press, 1984.

Berndt, B. C. Ramanujan's Notebooks, Part IV. New York: Springer-Verlag, 1994.

Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, pp. 94-96, 1996.

Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 40-45 and 64-68, 1985.

Honsberger, R. More Mathematical Morsels. Washington, DC: Math. Assoc. Amer., pp. 237-239, 1991.

Jackson, D. and Goulden, I. Combinatorial Enumeration. New York: Academic Press, 1983.

MacMahon, P. A. Combinatory Analysis. New York: Chelsea, 1960.

Rademacher, H. ``On the Partition Function $p(n)$.'' Proc. London Math. Soc. 43, 241-254, 1937.

Ruskey, F. ``Information of Numerical Partitions.'' http://sue.csc.uvic.ca/~cos/inf/nump/NumPartition.html.

Sloane, N. J. A. Sequences A000009/M0281, A000041/M0663, A000700/M0217, A001318/M1336, A046063, and A046064 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.