§26.10 Integer Partitions: Other Restrictions

Referenced by:: §27.14(vi)
Permalink:: http://dlmf.nist.gov/26.10

§26.10(i) Definitions
§26.10(ii) Generating Functions
§26.10(iii) Recurrence Relations
§26.10(iv) Identities
§26.10(v) Limiting Form
§26.10(vi) Bessel-Function Expansion

§26.10(i) Definitions

Notes:: Table 26.10.1 was computed by the author.
Defines:: $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$
Keywords:: restricted integer partitions
Permalink:: http://dlmf.nist.gov/26.10.i

$\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\ \;\;(\mathop{{\rm mod}}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.$

Symbols:: $\in$ : element of, $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $k$ : nonnegative integer and $S$ : set
Permalink:: http://dlmf.nist.gov/26.10.E1
Encodings:: TeX, pMML, png

Table 26.10.1: Partitions restricted by difference conditions, or equivalently with parts from $A_{{j,k}}$ .

	$\mathop{p\/}\nolimits\!\left(\mathcal{D},n\right)$	$\mathop{p\/}\nolimits\!\left(\mathcal{D}2,n\right)$	$\mathop{p\/}\nolimits\!\left(\mathcal{D}2,\hbox{}\!\!\in\! T,n\right)$	$\mathop{p\/}\nolimits\!\left(\mathcal{D}^{{\prime}}3,n\right)$
$n$	and	and	and	and
	$\mathop{p\/}\nolimits\!\left(\mathcal{O},n\right)$	$\mathop{p\/}\nolimits\!\left(\in\! A_{{1,5}},n\right)$	$\mathop{p\/}\nolimits\!\left(\in\! A_{{2,5}},n\right)$	$\mathop{p\/}\nolimits\!\left(\in\! A_{{1,6}},n\right)$
0	1	1	1	1
1	1	1	0	1
2	1	1	1	1
3	2	1	1	1
4	2	2	1	1
5	3	2	1	2
6	4	3	2	2
7	5	3	2	3
8	6	4	3	3
9	8	5	3	3
10	10	6	4	4
11	12	7	4	5
12	15	9	6	6
13	18	10	6	7
14	22	12	8	8
15	27	14	9	9
16	32	17	11	10
17	38	19	12	12
18	46	23	15	14
19	54	26	16	16
20	64	31	20	18

Symbols:: $\in$ : element of, $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $j$ : nonnegative integer, $k$ : nonnegative integer, $n$ : nonnegative integer, $A_{{j,k}}$ : set and $T$ : set
Keywords:: restricted integer partitions
Referenced by:: §26.10(i), §26.10(i)
Permalink:: http://dlmf.nist.gov/26.10.T1

§26.10(ii) Generating Functions

Notes:: See Andrews (1976, pp. 5, 16, 17, 19, 36). For (26.10.3) see Bressoud (1999, pp. 78–79).
Keywords:: restricted integer partitions
Permalink:: http://dlmf.nist.gov/26.10.ii

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}}),$

Symbols:: $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $j$ : nonnegative integer, $m$ : nonnegative integer, $n$ : nonnegative integer and $q$ : parameter
A&S Ref:: 24.2.2
Permalink:: http://dlmf.nist.gov/26.10.E2
Encodings:: TeX, pMML, png

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$ ,

Symbols:: $\genfrac{[}{]}{0.0pt}{}{n}{m}_{{q}}$ : $q$ -binomial coefficient (or Gaussian polynomial), $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $x$ : real variable, $j$ : nonnegative integer, $k$ : nonnegative integer, $m$ : nonnegative integer, $n$ : nonnegative integer and $q$ : parameter
Referenced by:: §26.10(ii)
Permalink:: http://dlmf.nist.gov/26.10.E3
Encodings:: TeX, pMML, png

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})}},$

Symbols:: $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $k$ : nonnegative integer, $m$ : nonnegative integer, $n$ : nonnegative integer and $q$ : parameter
Permalink:: http://dlmf.nist.gov/26.10.E4
Encodings:: TeX, pMML, png

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}}.$

Symbols:: $\in$ : element of, $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $j$ : nonnegative integer, $n$ : nonnegative integer, $S$ : set and $q$ : parameter
Permalink:: http://dlmf.nist.gov/26.10.E5
Encodings:: TeX, pMML, png

§26.10(iii) Recurrence Relations

Notes:: See Bressoud (1999, p. 60) and Andrews (1976, pp. 11, 12).
Keywords:: restricted integer partitions
Permalink:: http://dlmf.nist.gov/26.10.iii

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 _{{\substack{j\divides t\\ \mbox{\scriptsize$j$ odd}}}}j,$

Symbols:: $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $j$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.10.E6
Encodings:: TeX, pMML, png

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(\mathrm{condition},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

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(\mathrm{condition},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

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 $\mathop{p_{{m}}\/}\nolimits\!\left(\mathcal{D},n\right)=\mathop{p_{{m}}\/}\nolimits\!\left(\mathcal{D},n-m\right)+\mathop{p_{{m-1}}\/}\nolimits\!\left(\mathcal{D},n\right),$

Symbols:: $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $m$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.10.E9
Encodings:: TeX, pMML, png

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

Symbols:: $\mathop{p\/}\nolimits\!\left(n\right)$ : total number of partitions of $n$ , $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $k$ : nonnegative integer, $m$ : nonnegative integer and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.10.E10
Encodings:: TeX, pMML, png

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 _{{\substack{j\divides t\\ j\in S}}}j,$

Symbols:: $\in$ : element of, $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $j$ : nonnegative integer, $n$ : nonnegative integer and $S$ : set
Permalink:: http://dlmf.nist.gov/26.10.E11
Encodings:: TeX, pMML, png

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

§26.10(iv) Identities

Notes:: See Andrews (1976, pp. 5, 104, 116).
Keywords:: Rogers–Ramanujan identities, partitions, restricted integer partitions
Permalink:: http://dlmf.nist.gov/26.10.iv

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(\mathrm{condition},n\right)$ : restricted number of partions of $n$ and $n$ : nonnegative integer
Permalink:: http://dlmf.nist.gov/26.10.E12
Encodings:: TeX, pMML, png

26.10.13 $\mathop{p\/}\nolimits\!\left(\mathcal{D}2,n\right)=\mathop{p\/}\nolimits\!\left(\in A_{{1,5}},n\right),$

Symbols:: $\in$ : element of, $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions 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

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\}$ ,

Symbols:: $\in$ : element of, $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $\{\ldots\}$ : sequence, asymptotic sequence (or scale), or enumerable set, $n$ : nonnegative integer, $A_{{j,k}}$ : set and $T$ : set
Referenced by:: §26.10(iv)
Permalink:: http://dlmf.nist.gov/26.10.E14
Encodings:: TeX, pMML, png

26.10.15 $\mathop{p\/}\nolimits\!\left(\mathcal{D}^{{\prime}}3,n\right)=\mathop{p\/}\nolimits\!\left(\in A_{{1,6}},n\right).$

Symbols:: $\in$ : element of, $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $n$ : nonnegative integer and $A_{{j,k}}$ : set
Permalink:: http://dlmf.nist.gov/26.10.E15
Encodings:: TeX, pMML, png

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

Notes:: See Andrews (1976, p. 97).
Keywords:: restricted integer partitions
Permalink:: http://dlmf.nist.gov/26.10.v

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

Symbols:: $e$ : base of exponential function, $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of $n$ , $\sim$ : asymptotic equality and $n$ : nonnegative integer
A&S Ref:: 24.2.2
Permalink:: http://dlmf.nist.gov/26.10.E16
Encodings:: TeX, pMML, png

§26.10(vi) Bessel-Function Expansion

Notes:: See Andrews (1976, p. 82).
Keywords:: partitions, restricted integer partitions
Permalink:: http://dlmf.nist.gov/26.10.vi

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),$