# §26.10 Integer Partitions: Other Restrictions

## §26.10(i) Definitions

$\mathop{p\/}\nolimits\!\left(\mathcal{D},n\right)$ denotes the number of partitions of $n$ into distinct parts. $\mathop{p_{m}\/}\nolimits\!\left(\mathcal{D},n\right)$ denotes the number of partitions of $n$ into at most $m$ distinct parts. $\mathop{p\/}\nolimits\!\left(\mathcal{D}k,n\right)$ denotes the number of partitions of $n$ into parts with difference at least $k$. $\mathop{p\/}\nolimits\!\left(\mathcal{D}^{\prime}3,n\right)$ denotes the number of partitions of $n$ into parts with difference at least 3, except that multiples of 3 must differ by at least 6. $\mathop{p\/}\nolimits\!\left(\mathcal{O},n\right)$ denotes the number of partitions of $n$ into odd parts. $\mathop{p\/}\nolimits\!\left(\in\!S,n\right)$ denotes the number of partitions of $n$ into parts taken from the set $S$. The set $\{n\geq 1\>|\>n\equiv\pm j\ \pmod{k}\}$ is denoted by $A_{j,k}$. The set $\{2,3,4,\ldots\}$ is denoted by $T$. If more than one restriction applies, then the restrictions are separated by commas, for example, $\mathop{p\/}\nolimits\!\left(\mathcal{D}2,\hbox{}\!\!\in\!T,n\right)$. See Table 26.10.1.

 26.10.1 $\mathop{p\/}\nolimits\!\left(\mathcal{D},0\right)=\mathop{p\/}\nolimits\!\left% (\mathcal{D}k,0\right)=\mathop{p\/}\nolimits\!\left(\in\!S,0\right)=1.$

## §26.10(ii) Generating Functions

Throughout this subsection it is assumed that $|q|<1$.

 26.10.2 $\sum_{n=0}^{\infty}\mathop{p\/}\nolimits\!\left(\mathcal{D},n\right)q^{n}=% \prod_{j=1}^{\infty}(1+q^{j})=\prod_{j=1}^{\infty}\frac{1}{1-q^{2j-1}}=1+\sum_% {m=1}^{\infty}\frac{q^{m(m+1)/2}}{(1-q)(1-q^{2})\cdots(1-q^{m})}=1+\sum_{m=1}^% {\infty}q^{m}(1+q)(1+q^{2})\cdots\*(1+q^{m-1}),$

where the last right-hand side is the sum over $m\geq 0$ of the generating functions for partitions into distinct parts with largest part equal to $m$.

 26.10.3 $(1-x)\sum_{m,n=0}^{\infty}\mathop{p_{m}\/}\nolimits\!\left(\leq k,\mathcal{D},% n\right)x^{m}q^{n}=\sum_{m=0}^{k}\genfrac{[}{]}{0.0pt}{}{k}{m}_{q}q^{m(m+1)/2}% x^{m}=\prod_{j=1}^{k}(1+x\,q^{j}),$ $|x|<1$,
 26.10.4 $\sum_{n=0}^{\infty}\mathop{p\/}\nolimits\!\left(\mathcal{D}k,n\right)q^{n}={1+% \sum_{m=1}^{\infty}\frac{q^{(km^{2}+(2-k)m)/2}}{(1-q)(1-q^{2})\cdots(1-q^{m})}},$
 26.10.5 $\sum_{n=0}^{\infty}\mathop{p\/}\nolimits\!\left(\in\!S,n\right)q^{n}=\prod_{j% \in S}\frac{1}{1-q^{j}}.$

## §26.10(iii) Recurrence Relations

 26.10.6 $\mathop{p\/}\nolimits\!\left(\mathcal{D},n\right)=\frac{1}{n}\sum_{t=1}^{n}% \mathop{p\/}\nolimits\!\left(\mathcal{D},n-t\right)\sum_{\begin{subarray}{c}j% \mathbin{|}t\\ \mbox{\scriptsizej odd}\end{subarray}}j,$

where the inner sum is the sum of all positive odd divisors of $t$.

 26.10.7 $\sum(-1)^{k}\mathop{p\/}\nolimits\!\left(\mathcal{D},n-\tfrac{1}{2}(3k^{2}\pm k% )\right)=\begin{cases}(-1)^{r},&n=3r^{2}\pm r,\\ 0,&\mbox{otherwise},\end{cases}$ Symbols: $\mathop{p\/}\nolimits\!\left(\NVar{\mathrm{condition}},\NVar{n}\right)$: restricted number of partions of $n$, $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.2.2 Permalink: http://dlmf.nist.gov/26.10.E7 Encodings: TeX, pMML, png See also: Annotations for 26.10(iii)

where the sum is over nonnegative integer values of $k$ for which $n-\frac{1}{2}(3k^{2}\pm k)\geq 0$.

 26.10.8 $\sum(-1)^{k}\mathop{p\/}\nolimits\!\left(\mathcal{D},n-(3k^{2}\pm k)\right)=% \begin{cases}1,&n=\tfrac{1}{2}(r^{2}\pm r),\\ 0,&\mbox{otherwise},\end{cases}$ Symbols: $\mathop{p\/}\nolimits\!\left(\NVar{\mathrm{condition}},\NVar{n}\right)$: restricted number of partions of $n$, $k$: nonnegative integer and $n$: nonnegative integer A&S Ref: 24.2.2 Permalink: http://dlmf.nist.gov/26.10.E8 Encodings: TeX, pMML, png See also: Annotations for 26.10(iii)

where the sum is over nonnegative integer values of $k$ for which $n-(3k^{2}\pm k)\geq 0$.

In exact analogy with (26.9.8), we have

 26.10.9 $\displaystyle\mathop{p_{m}\/}\nolimits\!\left(\mathcal{D},n\right)$ $\displaystyle=\mathop{p_{m}\/}\nolimits\!\left(\mathcal{D},n-m\right)+\mathop{% p_{m-1}\/}\nolimits\!\left(\mathcal{D},n\right),$ 26.10.10 $\displaystyle\mathop{p\/}\nolimits\!\left(\mathcal{D}k,n\right)$ $\displaystyle=\sum\mathop{p_{m}\/}\nolimits\!\left(n-\tfrac{1}{2}km^{2}-m+% \tfrac{1}{2}km\right),$

where the sum is over nonnegative integer values of $m$ for which $n-\tfrac{1}{2}km^{2}-m+\tfrac{1}{2}km\geq 0$.

 26.10.11 $\mathop{p\/}\nolimits\!\left(\in\!S,n\right)=\frac{1}{n}\sum_{t=1}^{n}\mathop{% p\/}\nolimits\!\left(\in\!S,n-t\right)\sum_{\begin{subarray}{c}j\mathbin{|}t\\ j\in S\end{subarray}}j,$

where the inner sum is the sum of all positive divisors of $t$ that are in $S$.

## §26.10(iv) Identities

Equations (26.10.13) and (26.10.14) are the Rogers–Ramanujan identities. See also §17.2(vi).

 26.10.12 $\mathop{p\/}\nolimits\!\left(\mathcal{D},n\right)=\mathop{p\/}\nolimits\!\left% (\mathcal{O},n\right),$ Symbols: $\mathop{p\/}\nolimits\!\left(\NVar{\mathrm{condition}},\NVar{n}\right)$: restricted number of partions of $n$ and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.10.E12 Encodings: TeX, pMML, png See also: Annotations for 26.10(iv)
 26.10.13 $\mathop{p\/}\nolimits\!\left(\mathcal{D}2,n\right)=\mathop{p\/}\nolimits\!% \left(\in A_{1,5},n\right),$
 26.10.14 $\mathop{p\/}\nolimits\!\left(\mathcal{D}2,\hbox{}\!\!\in T,n\right)=\mathop{p% \/}\nolimits\!\left(\in\!A_{2,5},n\right),$ $T=\{2,3,4,\ldots\}$,
 26.10.15 $\mathop{p\/}\nolimits\!\left(\mathcal{D}^{\prime}3,n\right)=\mathop{p\/}% \nolimits\!\left(\in A_{1,6},n\right).$

Note that $\mathop{p\/}\nolimits\!\left(\mathcal{D}^{\prime}3,n\right)\leq\mathop{p\/}% \nolimits\!\left(\mathcal{D}3,n\right)$, with strict inequality for $n\geq 9$. It is known that for $k>3$, $\mathop{p\/}\nolimits\!\left(\mathcal{D}k,n\right)\geq\mathop{p\/}\nolimits\!% \left(\in\!A_{1,k+3},n\right)$, with strict inequality for $n$ sufficiently large, provided that $k=2^{m}-1,m=3,4,5$, or $k\geq 32$; see Yee (2004).

## §26.10(v) Limiting Form

 26.10.16 $\mathop{p\/}\nolimits\!\left(\mathcal{D},n\right)\sim\frac{{\mathrm{e}^{\pi% \sqrt{n/3}}}}{(768n^{3})^{1/4}},$ $n\to\infty$.

## §26.10(vi) Bessel-Function Expansion

 26.10.17 $\mathop{p\/}\nolimits\!\left(\mathcal{D},n\right)=\pi\sum_{k=1}^{\infty}\frac{% A_{2k-1}(n)}{(2k-1)\sqrt{24n+1}}\mathop{I_{1}\/}\nolimits\!\left(\frac{\pi}{2k% -1}\sqrt{\frac{24n+1}{72}}\right),$

where $\mathop{I_{1}\/}\nolimits\!\left(x\right)$ is the modified Bessel function (§10.25(ii)), and

 26.10.18 $A_{k}(n)=\sum_{\begin{subarray}{c}1

with

 26.10.19 $f(h,k)=\sum_{j=1}^{k}\left[\!\!\left[\frac{2j-1}{2k}\right]\!\!\right]\left[\!% \!\left[\frac{h(2j-1)}{k}\right]\!\!\right],$ Defines: $f(h,k)$: function (locally) Symbols: $h$: nonnegative integer, $j$: nonnegative integer and $k$: nonnegative integer Permalink: http://dlmf.nist.gov/26.10.E19 Encodings: TeX, pMML, png See also: Annotations for 26.10(vi)

and

 26.10.20 $[\![x]\!]=\begin{cases}x-\left\lfloor x\right\rfloor-\tfrac{1}{2},&x\notin% \mathbb{Z},\\ 0,&x\in\mathbb{Z}.\end{cases}$

The quantity $A_{k}(n)$ is real-valued.