# §26.10 Integer Partitions: Other Restrictions

## §26.10(i) Definitions

$p\left(\mathcal{D},n\right)$ denotes the number of partitions of $n$ into distinct parts. $p_{m}\left(\mathcal{D},n\right)$ denotes the number of partitions of $n$ into at most $m$ distinct parts. $p\left(\mathcal{D}k,n\right)$ denotes the number of partitions of $n$ into parts with difference at least $k$. $p\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. $p\left(\mathcal{O},n\right)$ denotes the number of partitions of $n$ into odd parts. $p\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, $p\left(\mathcal{D}2,\hbox{}\!\!\in\!T,n\right)$. See Table 26.10.1.

 26.10.1 $p\left(\mathcal{D},0\right)=p\left(\mathcal{D}k,0\right)=p\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}p\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}p_{m}\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}p\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}p\left(\in\!S,n\right)q^{n}=\prod_{j\in S}\frac{1}{1-q^{j}}.$

## §26.10(iii) Recurrence Relations

 26.10.6 $p\left(\mathcal{D},n\right)=\frac{1}{n}\sum_{t=1}^{n}p\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}p\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: $p\left(\NVar{\mathrm{condition}},\NVar{n}\right)$: restricted number of partitions 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), §26.10 and Ch.26

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}p\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: $p\left(\NVar{\mathrm{condition}},\NVar{n}\right)$: restricted number of partitions 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), §26.10 and Ch.26

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 p_{m}\left(\mathcal{D},n\right)$ $\displaystyle=p_{m}\left(\mathcal{D},n-m\right)+p_{m-1}\left(\mathcal{D},n% \right),$ 26.10.10 $\displaystyle p\left(\mathcal{D}k,n\right)$ $\displaystyle=\sum p_{m}\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 $p\left(\in\!S,n\right)=\frac{1}{n}\sum_{t=1}^{n}p\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

 26.10.12 $p\left(\mathcal{D},n\right)=p\left(\mathcal{O},n\right),$ ⓘ Symbols: $p\left(\NVar{\mathrm{condition}},\NVar{n}\right)$: restricted number of partitions 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 and Ch.26
 26.10.13 $p\left(\mathcal{D}2,n\right)=p\left(\in A_{1,5},n\right),$ ⓘ Symbols: $\in$: element of, $p\left(\NVar{\mathrm{condition}},\NVar{n}\right)$: restricted number of partitions of $n$, $n$: nonnegative integer and $A_{j,k}$: set Referenced by: §26.10(iv) Permalink: http://dlmf.nist.gov/26.10.E13 Encodings: TeX, pMML, png See also: Annotations for §26.10(iv), §26.10 and Ch.26
 26.10.14 $p\left(\mathcal{D}2,\hbox{}\!\!\in T,n\right)=p\left(\in\!A_{2,5},n\right),$ $T=\{2,3,4,\ldots\}$,
 26.10.15 $p\left(\mathcal{D}^{\prime}3,n\right)=p\left(\in A_{1,6},n\right).$

Note that $p\left(\mathcal{D}^{\prime}3,n\right)\leq p\left(\mathcal{D}3,n\right)$, with strict inequality for $n\geq 9$. It is known that for $k>3$, $p\left(\mathcal{D}k,n\right)\geq p\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 $p\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 $p\left(\mathcal{D},n\right)=\pi\sum_{k=1}^{\infty}\frac{A_{2k-1}(n)}{(2k-1)% \sqrt{24n+1}}I_{1}\left(\frac{\pi}{2k-1}\sqrt{\frac{24n+1}{72}}\right),$

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

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), §26.10 and Ch.26

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.