§27.14 Unrestricted Partitions

Referenced by:: §26.9(i)
Permalink:: http://dlmf.nist.gov/27.14

§27.14(i) Partition Functions
§27.14(ii) Generating Functions and Recursions
§27.14(iii) Asymptotic Formulas
§27.14(iv) Relation to Modular Functions
§27.14(v) Divisibility Properties
§27.14(vi) Ramanujan’s Tau Function

§27.14(i) Partition Functions

Notes:: See Apostol (1976, p. 307).
Keywords:: additive number theory, partition function
Referenced by:: §17.16, §27.14(ii)
Permalink:: http://dlmf.nist.gov/27.14.i

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

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 $\mathop{p\/}\nolimits\!\left(n\right)$ , and the summands are called parts; see §26.9(i). For example, $\mathop{p\/}\nolimits\!\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 $\mathop{p_{{k}}\/}\nolimits\!\left(n\right)$ ; again see §26.9(i).

§27.14(ii) Generating Functions and Recursions

Notes:: See Apostol (1976, Chapter 14).
Keywords:: Euler’s pentagonal number theorem, additive number theory, number theory, partition function, pentagonal numbers
Permalink:: http://dlmf.nist.gov/27.14.ii

Euler introduced the reciprocal of the infinite product

27.14.2 $\mathop{\mathit{f}\/}\nolimits\!\left(x\right)=\prod _{{m=1}}^{\infty}(1-x^{m}),$ $|x|<1$ ,

Defines:: $\mathop{\mathit{f}\/}\nolimits\!\left(x\right)$ : Euler’s reciprocal function
Symbols:: $m$ : positive integer and $x$ : real number
Referenced by:: §27.14(iv), §27.21
Permalink:: http://dlmf.nist.gov/27.14.E2
Encodings:: TeX, pMML, png

as a generating function for the function $\mathop{p\/}\nolimits\!\left(n\right)$ defined in §27.14(i):

27.14.3 $\frac{1}{\mathop{\mathit{f}\/}\nolimits\!\left(x\right)}=\sum _{{n=0}}^{\infty}\mathop{p\/}\nolimits\!\left(n\right)x^{n},$

Symbols:: $\mathop{\mathit{f}\/}\nolimits\!\left(x\right)$ : Euler’s reciprocal function, $\mathop{p\/}\nolimits\!\left(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

with $\mathop{p\/}\nolimits\!\left(0\right)=1$ . Euler’s pentagonal number theorem states that

27.14.4 $\mathop{\mathit{f}\/}\nolimits\!\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:: $\mathop{\mathit{f}\/}\nolimits\!\left(x\right)$ : Euler’s reciprocal function, $\omega$ : pentagonal numbers, $k$ : positive integer and $x$ : real number
Permalink:: http://dlmf.nist.gov/27.14.E4
Encodings:: TeX, pMML, png

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$ : pentagonal numbers
Symbols:: $k$ : positive integer
Permalink:: http://dlmf.nist.gov/27.14.E5
Encodings:: TeX, pMML, png

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

27.14.6 $\mathop{p\/}\nolimits\!\left(n\right)=\sum _{{k=1}}^{\infty}(-1)^{{k+1}}\left(\mathop{p\/}\nolimits\!\left(n-\omega(k)\right)+\mathop{p\/}\nolimits\!\left(n-\omega(-k)\right)\right)=\mathop{p\/}\nolimits\!\left(n-1\right)+\mathop{p\/}\nolimits\!\left(n-2\right)-\mathop{p\/}\nolimits\!\left(n-5\right)-\mathop{p\/}\nolimits\!\left(n-7\right)+\cdots,$

Symbols:: $\mathop{p\/}\nolimits\!\left(n\right)$ : total number of partitions of $n$ , $\omega$ : pentagonal numbers, $k$ : positive integer and $n$ : positive integer
A&S Ref:: 24.2.1 II.A (in slightly different form)
Referenced by:: §27.20
Permalink:: http://dlmf.nist.gov/27.14.E6
Encodings:: TeX, pMML, png

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

27.14.7 $n\mathop{p\/}\nolimits\!\left(n\right)=\sum _{{k=1}}^{n}\mathop{\sigma _{{1}}\/}\nolimits\!\left(n\right)\mathop{p\/}\nolimits\!\left(n-k\right),$

Symbols:: $\mathop{\sigma _{{\alpha}}\/}\nolimits\!\left(n\right)$ : sum of powers of divisors of $n$ , $\mathop{p\/}\nolimits\!\left(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)
Referenced by:: §27.20
Permalink:: http://dlmf.nist.gov/27.14.E7
Encodings:: TeX, pMML, png

where $\mathop{\sigma _{{1}}\/}\nolimits\!\left(n\right)$ is defined by (27.2.10) with $\alpha=1$ .

§27.14(iii) Asymptotic Formulas

Notes:: See Apostol (1990, Chapters 3–5).
Keywords:: Dedekind sums, additive number theory, number theory, partition function
Referenced by:: ¶ ‣ §23.18
Permalink:: http://dlmf.nist.gov/27.14.iii

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

27.14.8 $\mathop{p\/}\nolimits\!\left(n\right)\sim e^{{K\sqrt{n}}}/(4n\sqrt{3}),$

Symbols:: $e$ : base of exponential function, $\mathop{p\/}\nolimits\!\left(n\right)$ : total number of partitions of $n$ , $\sim$ : asymptotic equality and $n$ : positive integer
A&S Ref:: 24.2.1 III
Permalink:: http://dlmf.nist.gov/27.14.E8
Encodings:: TeX, pMML, png

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

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

Symbols:: $\frac{df}{dx}$ : derivative of $f$ with respect to $x$ , $\mathop{\sinh\/}\nolimits z$ : hyperbolic sine function, $\mathop{p\/}\nolimits\!\left(n\right)$ : total number of partitions of $n$ , $k$ : positive integer, $n$ : positive integer and $A_{k}(n)$ : coefficients
A&S Ref:: 24.2.1 I.C
Permalink:: http://dlmf.nist.gov/27.14.E9
Encodings:: TeX, pMML, png

where

27.14.10 $A_{k}(n)=\sum _{{\substack{h=1\\ \left(h,k\right)=1}}}^{k}\mathop{\exp\/}\nolimits\!\left(\pi is(h,k)-2\pi in\frac{h}{k}\right),$

Symbols:: $s$ : Dedekind sum, $\mathop{\exp\/}\nolimits z$ : exponential function, $k$ : positive integer, $n$ : positive integer and $A_{k}(n)$ : coefficients
A&S Ref:: 24.2.1 I.C
Permalink:: http://dlmf.nist.gov/27.14.E10
Encodings:: TeX, pMML, png

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$ : Dedekind sum
Symbols:: $\left\lfloor x\right\rfloor$ : floor of $x$ and $k$ : positive integer
A&S Ref:: 24.2.1 I.C
Referenced by:: §27.14(iv)
Permalink:: http://dlmf.nist.gov/27.14.E11
Encodings:: TeX, pMML, png

§27.14(iv) Relation to Modular Functions

Notes:: See Apostol (1990, Chapters 3–5).
Keywords:: Dedekind modular function, additive number theory
Referenced by:: §23.20(v)
Permalink:: http://dlmf.nist.gov/27.14.iv

Dedekind sums occur in the transformation theory of the Dedekind modular function $\mathop{\eta\/}\nolimits\!\left(\tau\right)$ , defined by

27.14.12 $\mathop{\eta\/}\nolimits\!\left(\tau\right)=e^{{\pi i\tau/12}}\prod _{{n=1}}^{\infty}(1-e^{{2\pi in\tau}}),$ $\imagpart{\tau}>0$ .

Defines:: $\mathop{\eta\/}\nolimits\!\left(\tau\right)$ : Dedekind’s eta function (or Dedekind modular function)
Symbols:: $e$ : base of exponential function, $\imagpart{}$ : imaginary part and $n$ : positive integer
Referenced by:: §27.14(vi)
Permalink:: http://dlmf.nist.gov/27.14.E12
Encodings:: TeX, pMML, png

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

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

Symbols:: $\mathop{\eta\/}\nolimits\!\left(\tau\right)$ : Dedekind’s eta function (or Dedekind modular function), $\mathop{\mathit{f}\/}\nolimits\!\left(x\right)$ : Euler’s reciprocal function, $e$ : base of exponential function and $\imagpart{}$ : imaginary part
Permalink:: http://dlmf.nist.gov/27.14.E13
Encodings:: TeX, pMML, png

$\mathop{\eta\/}\nolimits\!\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 $\mathop{\eta\/}\nolimits\!\left(\frac{a\tau+b}{c\tau+d}\right)=\varepsilon(-i(c\tau+d))^{{\frac{1}{2}}}\mathop{\eta\/}\nolimits\!\left(\tau\right),$

Symbols:: $\mathop{\eta\/}\nolimits\!\left(\tau\right)$ : Dedekind’s eta function (or Dedekind modular function), $\imagpart{}$ : imaginary part, $a$ : integer, $b$ : integer, $c$ : integer and $d$ : integer
Permalink:: http://dlmf.nist.gov/27.14.E14
Encodings:: TeX, pMML, png

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

For further properties of the function $\mathop{\eta\/}\nolimits\!\left(\tau\right)$ see §§23.15–23.19.

§27.14(v) Divisibility Properties

Notes:: See Apostol (1976, Chapter 14).
Keywords:: Ramanujan’s partition identity, additive number theory, number theory, partition function
Permalink:: http://dlmf.nist.gov/27.14.v

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

27.14.15 $5\frac{(\mathop{\mathit{f}\/}\nolimits\!\left(x^{5}\right))^{5}}{(\mathop{\mathit{f}\/}\nolimits\!\left(x\right))^{6}}=\sum _{{n=0}}^{\infty}\mathop{p\/}\nolimits\!\left(5n+4\right)x^{n}$

Symbols:: $\mathop{\mathit{f}\/}\nolimits\!\left(x\right)$ : Euler’s reciprocal function, $\mathop{p\/}\nolimits\!\left(n\right)$ : total number of partitions of $n$ , $n$ : positive integer and $x$ : real number
Permalink:: http://dlmf.nist.gov/27.14.E15
Encodings:: TeX, pMML, png

implies $\mathop{p\/}\nolimits\!\left(5n+4\right)\equiv 0\;\;(\mathop{{\rm mod}}5)$ . Ramanujan also found that $\mathop{p\/}\nolimits\!\left(7n+5\right)\equiv 0\;\;(\mathop{{\rm mod}}7)$ and $\mathop{p\/}\nolimits\!\left(11n+6\right)\equiv 0\;\;(\mathop{{\rm mod}}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 $\mathop{p\/}\nolimits\!\left(an+b\right)\equiv 0\;\;(\mathop{{\rm mod}}q)$ for all $n$ . For example, $\mathop{p\/}\nolimits\!\left(1575\; 25693n+1\; 11247\right)\equiv 0\;\;(\mathop{{\rm mod}}13)$ .

§27.14(vi) Ramanujan’s Tau Function

Notes:: See Apostol (1990, Chapters 3–5).
Keywords:: Ramanujan’s tau function, additive number theory, discriminant function, number theory
Permalink:: http://dlmf.nist.gov/27.14.vi

The discriminant function $\mathop{\Delta\/}\nolimits\!\left(\tau\right)$ is defined by

27.14.16 $\mathop{\Delta\/}\nolimits\!\left(\tau\right)=(2\pi)^{{12}}(\mathop{\eta\/}\nolimits\!\left(\tau\right))^{{24}},$ $\imagpart{\tau}>0$ ,

Defines:: $\mathop{\Delta\/}\nolimits\!\left(\tau\right)$ : discriminant function
Symbols:: $\mathop{\eta\/}\nolimits\!\left(\tau\right)$ : Dedekind’s eta function (or Dedekind modular function) and $\imagpart{}$ : imaginary part
Permalink:: http://dlmf.nist.gov/27.14.E16
Encodings:: TeX, pMML, png

and satisfies the functional equation

27.14.17 $\mathop{\Delta\/}\nolimits\!\left(\frac{a\tau+b}{c\tau+d}\right)=(c\tau+d)^{{12}}\mathop{\Delta\/}\nolimits\!\left(\tau\right),$

Symbols:: $\mathop{\Delta\/}\nolimits\!\left(\tau\right)$ : discriminant function and $\imagpart{}$ : imaginary part
Permalink:: http://dlmf.nist.gov/27.14.E17
Encodings:: TeX, pMML, png

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

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

27.14.18 $x\prod _{{n=1}}^{\infty}(1-x^{n})^{{24}}=\sum _{{n=1}}^{\infty}\mathop{\tau\/}\nolimits\!\left(n\right)x^{n},$ $|x|<1$ .

Defines:: $\mathop{\tau\/}\nolimits\!\left(n\right)$ : Ramanujan’s tau function
Symbols:: $n$ : positive integer and $x$ : real number
Referenced by:: §27.20
Permalink:: http://dlmf.nist.gov/27.14.E18
Encodings:: TeX, pMML, png

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

27.14.19 $\mathop{\tau\/}\nolimits\!\left(m\right)\mathop{\tau\/}\nolimits\!\left(n\right)=\sum _{{d\divides\left(m,n\right)}}d^{{11}}\mathop{\tau\/}\nolimits\!\left(\frac{mn}{d^{2}}\right),$ $m,n=1,2,\dots$ .

Symbols:: $\mathop{\tau\/}\nolimits\!\left(n\right)$ : Ramanujan’s tau function, $m$ : positive integer and $n$ : positive integer
Permalink:: http://dlmf.nist.gov/27.14.E19
Encodings:: TeX, pMML, png

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

27.14.20 $\mathop{\tau\/}\nolimits\!\left(n\right)\equiv\mathop{\sigma _{{11}}\/}\nolimits\!\left(n\right)\;\;(\mathop{{\rm mod}}691).$

Symbols:: $\mathop{\tau\/}\nolimits\!\left(n\right)$ : Ramanujan’s tau function, $\mathop{\sigma _{{\alpha}}\/}\nolimits\!\left(n\right)$ : sum of powers of divisors of $n$ and $n$ : positive integer
Referenced by:: §27.20
Permalink:: http://dlmf.nist.gov/27.14.E20
Encodings:: TeX, pMML, png

For further information on partitions and generating functions see Andrews (1976); also §§17.2–17.14, and §§26.9–26.10.