# §27.14 Unrestricted Partitions

## §27.14(i) Partition Functions

A fundamental problem studies the number of ways $n$ can be written as a sum of positive integers $\leq n$, that is, the number of solutions of

 27.14.1 $n=a_{1}+a_{2}+\cdots,$ $a_{1}\geq a_{2}\geq\cdots\geq 1$. ⓘ Symbols: $n$: positive integer Permalink: http://dlmf.nist.gov/27.14.E1 Encodings: TeX, pMML, png See also: Annotations for §27.14(i), §27.14 and Ch.27

The number of summands is unrestricted, repetition is allowed, and the order of the summands is not taken into account. The corresponding unrestricted partition function is denoted by $p\left(n\right)$, and the summands are called parts; see §26.9(i). For example, $p\left(5\right)=7$ because there are exactly seven partitions of $5$: $5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1$.

The number of partitions of $n$ into at most $k$ parts is denoted by $p_{k}\left(n\right)$; again see §26.9(i).

## §27.14(ii) Generating Functions and Recursions

Euler introduced the reciprocal of the infinite product

 27.14.2 $\mathit{f}\left(x\right)=\prod_{m=1}^{\infty}(1-x^{m})=\left(x;x\right)_{% \infty},$ $|x|<1$, ⓘ Defines: $\mathit{f}\left(\NVar{x}\right)$: Euler’s reciprocal function Symbols: $\left(\NVar{a};\NVar{q}\right)_{\NVar{n}}$: $q$-Pochhammer symbol (or $q$-shifted factorial), $m$: positive integer and $x$: real number Referenced by: §27.14(iv), §27.21, Erratum (V1.0.28) for Equation (27.14.2) Permalink: http://dlmf.nist.gov/27.14.E2 Encodings: TeX, pMML, png Addition (effective with 1.0.28): The representation in terms of $\left(x;x\right)_{\infty}$ was added to this equation. See also: Annotations for §27.14(ii), §27.14 and Ch.27

as a generating function for the function $p\left(n\right)$ defined in §27.14(i):

 27.14.3 $\frac{1}{\mathit{f}\left(x\right)}=\sum_{n=0}^{\infty}p\left(n\right)x^{n},$ ⓘ Symbols: $\mathit{f}\left(\NVar{x}\right)$: Euler’s reciprocal function, $p\left(\NVar{n}\right)$: total number of partitions of $n$, $n$: positive integer and $x$: real number A&S Ref: 24.2.1 I.B Permalink: http://dlmf.nist.gov/27.14.E3 Encodings: TeX, pMML, png See also: Annotations for §27.14(ii), §27.14 and Ch.27

with $p\left(0\right)=1$. Euler’s pentagonal number theorem states that

 27.14.4 $\mathit{f}\left(x\right)=1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+\dots=1+\sum_{k=1% }^{\infty}(-1)^{k}\left(x^{\omega(k)}+x^{\omega(-k)}\right),$ ⓘ Symbols: $\mathit{f}\left(\NVar{x}\right)$: Euler’s reciprocal function, $k$: positive integer, $x$: real number and $\omega(k)$: pentagonal numbers Permalink: http://dlmf.nist.gov/27.14.E4 Encodings: TeX, pMML, png See also: Annotations for §27.14(ii), §27.14 and Ch.27

where the exponents $1$, $2$, $5$, $7$, $12$, $15$, $\dots$ are the pentagonal numbers, defined by

 27.14.5 $\omega(\pm k)=(3k^{2}\mp k)/2,$ $k=1,2,3,\dots$. ⓘ Defines: $\omega(k)$: pentagonal numbers (locally) Symbols: $k$: positive integer Permalink: http://dlmf.nist.gov/27.14.E5 Encodings: TeX, pMML, png See also: Annotations for §27.14(ii), §27.14 and Ch.27

Multiplying the power series for $\mathit{f}\left(x\right)$ with that for $1/\mathit{f}\left(x\right)$ and equating coefficients, we obtain the recursion formula

 27.14.6 $p\left(n\right)=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p\left(n-\omega(k)\right)+p% \left(n-\omega(-k)\right)\right)=p\left(n-1\right)+p\left(n-2\right)-p\left(n-% 5\right)-p\left(n-7\right)+\cdots,$ ⓘ Symbols: $p\left(\NVar{n}\right)$: total number of partitions of $n$, $k$: positive integer, $n$: positive integer and $\omega(k)$: pentagonal numbers A&S Ref: 24.2.1 II.A (in slightly different form) Referenced by: §27.20, §27.20 Permalink: http://dlmf.nist.gov/27.14.E6 Encodings: TeX, pMML, png See also: Annotations for §27.14(ii), §27.14 and Ch.27

where $p\left(k\right)$ is defined to be $0$ if $k<0$. Logarithmic differentiation of the generating function $1/\mathit{f}\left(x\right)$ leads to another recursion:

 27.14.7 $np\left(n\right)=\sum_{k=1}^{n}\sigma_{1}\left(k\right)p\left(n-k\right),$ ⓘ Symbols: $\sigma_{\NVar{\alpha}}\left(\NVar{n}\right)$: sum of powers of divisors of $n$, $p\left(\NVar{n}\right)$: total number of partitions of $n$, $k$: positive integer and $n$: positive integer A&S Ref: 24.2.1 II.A (in slightly different form) 24.2.1 II.A (in slightly different form) Referenced by: §27.20, §27.20, Erratum (V1.0.11) for Clarifications Permalink: http://dlmf.nist.gov/27.14.E7 Encodings: TeX, pMML, png Errata (effective with 1.0.11): The erroneous $\sigma_{1}\left(n\right)$ in $np\left(n\right)=\sum_{k=1}^{n}\sigma_{1}\left(n\right)p\left(n-k\right)$ was replaced. Reported 2015-08-17 by Howard Cohl and Hannah Cohen See also: Annotations for §27.14(ii), §27.14 and Ch.27

where $\sigma_{1}\left(k\right)$ is defined by (27.2.10) with $\alpha=1$.

## §27.14(iii) Asymptotic Formulas

These recursions can be used to calculate $p\left(n\right)$, which grows very rapidly. For example, $p\left(10\right)=42,p\left(100\right)$ = $1905\;69292$, and $p\left(200\right)=397\;29990\;29388$. For large $n$

 27.14.8 $p\left(n\right)\sim e^{K\sqrt{n}}/(4n\sqrt{3}),$ ⓘ Symbols: $\sim$: asymptotic equality, $\mathrm{e}$: base of natural logarithm, $p\left(\NVar{n}\right)$: total number of partitions of $n$ and $n$: positive integer A&S Ref: 24.2.1 III Permalink: http://dlmf.nist.gov/27.14.E8 Encodings: TeX, pMML, png See also: Annotations for §27.14(iii), §27.14 and Ch.27

where $K=\pi\sqrt{2/3}$ (Hardy and Ramanujan (1918)). Rademacher (1938) derives a convergent series that also provides an asymptotic expansion for $p\left(n\right)$:

 27.14.9 $p\left(n\right)=\frac{1}{\pi\sqrt{2}}\sum_{k=1}^{\infty}\sqrt{k}A_{k}(n)\*% \left[\frac{\mathrm{d}}{\mathrm{d}t}\frac{\sinh\left(\ifrac{K\sqrt{t}}{k}% \right)}{\sqrt{t}}\right]_{t=n-(1/24)},$

where

 27.14.10 $A_{k}(n)=\sum_{\begin{subarray}{c}h=1\\ \left(h,k\right)=1\end{subarray}}^{k}\exp\left(\pi\mathrm{i}s(h,k)-2\pi\mathrm% {i}n\frac{h}{k}\right),$

and $s(h,k)$ is a Dedekind sum given by

 27.14.11 $s(h,k)=\sum_{r=1}^{k-1}\frac{r}{k}\left(\frac{hr}{k}-\left\lfloor\frac{hr}{k}% \right\rfloor-\frac{1}{2}\right).$ ⓘ Defines: $s(h,k)$: Dedekind sum (locally) Symbols: $\left\lfloor\NVar{x}\right\rfloor$: floor of $x$ and $k$: positive integer A&S Ref: 24.2.1 I.C Referenced by: §23.18, §27.14(iv) Permalink: http://dlmf.nist.gov/27.14.E11 Encodings: TeX, pMML, png See also: Annotations for §27.14(iii), §27.14 and Ch.27

## §27.14(iv) Relation to Modular Functions

Dedekind sums occur in the transformation theory of the Dedekind modular function $\eta\left(\tau\right)$, defined by

 27.14.12 $\eta\left(\tau\right)=e^{\pi\mathrm{i}\tau/12}\prod_{n=1}^{\infty}(1-e^{2\pi% \mathrm{i}n\tau}),$ $\Im\tau>0$. ⓘ Defines: $\eta\left(\NVar{\tau}\right)$: Dedekind’s eta function (or Dedekind modular function) Symbols: $\pi$: the ratio of the circumference of a circle to its diameter, $\mathrm{e}$: base of natural logarithm, $\Im$: imaginary part, $\mathrm{i}$: imaginary unit and $n$: positive integer Referenced by: §23.15(ii), §27.14(vi) Permalink: http://dlmf.nist.gov/27.14.E12 Encodings: TeX, pMML, png See also: Annotations for §27.14(iv), §27.14 and Ch.27

This is related to the function $\mathit{f}\left(x\right)$ in (27.14.2) by

 27.14.13 $\eta\left(\tau\right)=e^{\pi\mathrm{i}\tau/12}\mathit{f}\left(e^{2\pi\mathrm{i% }\tau}\right).$

$\eta\left(\tau\right)$ satisfies the following functional equation: if $a,b,c,d$ are integers with $ad-bc=1$ and $c>0$, then

 27.14.14 $\eta\left(\frac{a\tau+b}{c\tau+d}\right)=\varepsilon(-\mathrm{i}(c\tau+d))^{% \frac{1}{2}}\eta\left(\tau\right),$

where $\varepsilon=\exp\left(\pi\mathrm{i}(((a+d)/(12c))-s(d,c))\right)$ and $s(d,c)$ is given by (27.14.11).

For further properties of the function $\eta\left(\tau\right)$ see §§23.1523.19.

## §27.14(v) Divisibility Properties

Ramanujan (1921) gives identities that imply divisibility properties of the partition function. For example, the Ramanujan identity

 27.14.15 $5\frac{(\mathit{f}\left(x^{5}\right))^{5}}{(\mathit{f}\left(x\right))^{6}}=% \sum_{n=0}^{\infty}p\left(5n+4\right)x^{n}$

implies $p\left(5n+4\right)\equiv 0\pmod{5}$. Ramanujan also found that $p\left(7n+5\right)\equiv 0\pmod{7}$ and $p\left(11n+6\right)\equiv 0\pmod{11}$ for all $n$. After decades of nearly fruitless searching for further congruences of this type, it was believed that no others existed, until it was shown in Ono (2000) that there are infinitely many. Ono proved that for every prime $q>3$ there are integers $a$ and $b$ such that $p\left(an+b\right)\equiv 0\pmod{q}$ for all $n$. For example, $p\left(1575\;25693n+1\;11247\right)\equiv 0\pmod{13}$.

## §27.14(vi) Ramanujan’s Tau Function

The discriminant function $\Delta\left(\tau\right)$ is defined by

 27.14.16 $\Delta\left(\tau\right)=(2\pi)^{12}(\eta\left(\tau\right))^{24},$ $\Im\tau>0$, ⓘ Defines: $\Delta\left(\NVar{\tau}\right)$: discriminant function Symbols: $\eta\left(\NVar{\tau}\right)$: Dedekind’s eta function (or Dedekind modular function), $\pi$: the ratio of the circumference of a circle to its diameter and $\Im$: imaginary part Permalink: http://dlmf.nist.gov/27.14.E16 Encodings: TeX, pMML, png See also: Annotations for §27.14(vi), §27.14 and Ch.27

and satisfies the functional equation

 27.14.17 $\Delta\left(\frac{a\tau+b}{c\tau+d}\right)=(c\tau+d)^{12}\Delta\left(\tau% \right),$ ⓘ Symbols: $\Delta\left(\NVar{\tau}\right)$: discriminant function and $\Im$: imaginary part Permalink: http://dlmf.nist.gov/27.14.E17 Encodings: TeX, pMML, png See also: Annotations for §27.14(vi), §27.14 and Ch.27

if $a,b,c,d$ are integers with $ad-bc=1$ and $c>0$.

The 24th power of $\eta\left(\tau\right)$ in (27.14.12) with $e^{2\pi\mathrm{i}\tau}=x$ is an infinite product that generates a power series in $x$ with integer coefficients called Ramanujan’s tau function $\tau\left(n\right)$:

 27.14.18 $x\prod_{n=1}^{\infty}(1-x^{n})^{24}=\sum_{n=1}^{\infty}\tau\left(n\right)x^{n},$ $|x|<1$. ⓘ Defines: $\tau\left(\NVar{n}\right)$: Ramanujan’s tau function Symbols: $n$: positive integer and $x$: real number Referenced by: §27.20, §27.20 Permalink: http://dlmf.nist.gov/27.14.E18 Encodings: TeX, pMML, png See also: Annotations for §27.14(vi), §27.14 and Ch.27

The tau function is multiplicative and satisfies the more general relation:

 27.14.19 $\tau\left(m\right)\tau\left(n\right)=\sum_{d\mathbin{|}\left(m,n\right)}d^{11}% \tau\left(\frac{mn}{d^{2}}\right),$ $m,n=1,2,\dots$.

Lehmer (1947) conjectures that $\tau\left(n\right)$ is never 0 and verifies this for all $n<21\;49286\;39999$ by studying various congruences satisfied by $\tau\left(n\right)$, for example:

 27.14.20 $\tau\left(n\right)\equiv\sigma_{11}\left(n\right)\pmod{691}.$

For further information on partitions and generating functions see Andrews (1976); also §§17.217.14, and §§26.926.10.