26 Combinatorial Analysis Properties 26.9 Integer Partitions: Restricted Number and Part Size 26.11 Integer Partitions: Compositions

§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
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 into distinct parts. $\mathop{p_{{m}}\/}\nolimits\!\left(\mathcal{D},n\right)$ denotes the number of partitions of into at most distinct parts. $\mathop{p\/}\nolimits\!\left(\mathcal{D}k,n\right)$ denotes the number of partitions of into parts with difference at least . $\mathop{p\/}\nolimits\!\left(\mathcal{D}^{{\prime}}3,n\right)$ denotes the number of partitions of 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 into odd parts. $\mathop{p\/}\nolimits\!\left(\in\!S,n\right)$ denotes the number of partitions of into parts taken from the set . 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 . 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 , : nonnegative integer and : 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)$
	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 , : nonnegative integer, : nonnegative integer, : nonnegative integer, $A_{{j,k}}$ : set and : 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 .

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 , : nonnegative integer, : nonnegative integer, : nonnegative integer and : 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 .

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

Symbols:: $\genfrac{[}{]}{0.0pt}{}{n}{m}_{{q}}$ : -binomial coefficient (or Gaussian polynomial), $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of , : real variable, : nonnegative integer, : nonnegative integer, : nonnegative integer, : nonnegative integer and : 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 , : nonnegative integer, : nonnegative integer, : nonnegative integer and : 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 , : nonnegative integer, : nonnegative integer, : set and : 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 , : nonnegative integer and : 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 .

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

where the sum is over nonnegative integer values of 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 , : nonnegative integer, : nonnegative integer and : 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 that are in .

§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 and : 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 , : 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 , $\{\ldots\}$ : sequence, asymptotic sequence (or scale), or enumerable set, : nonnegative integer, $A_{{j,k}}$ : set and : 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 , : 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 , $\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 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:: : base of exponential function, $\mathop{p\/}\nolimits\!\left(\mathrm{condition},n\right)$ : restricted number of partions of , $\sim$ : asymptotic equality and : 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),$