26 Combinatorial Analysis Properties 26.8 Set Partitions: Stirling Numbers 26.10 Integer Partitions: Other Restrictions

§26.9 Integer Partitions: Restricted Number and Part Size

ⓘ

Keywords:: of integers, partitions
Referenced by:: §17.16, §27.14(vi)
Permalink:: http://dlmf.nist.gov/26.9
See also:: Annotations for Ch.26

§26.9(i) Definitions

ⓘ

Defines:: $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts and $p_{\NVar{k}}\left(\leq\NVar{m},\NVar{n}\right)$ : number of partitions of $n$ into at most $k$ parts, each less than or equal to $m$
Keywords:: Ferrers graph, conjugate, notation, partitions, relation to lattice paths, restricted integer partitions
Notes:: See Andrews (1976, pp. 1–13, 81). Table 26.9.1 was computed by the author.
Referenced by:: §26.17, §27.14(i), §27.14(i)
Permalink:: http://dlmf.nist.gov/26.9.i
See also:: Annotations for §26.9 and Ch.26

$p_{k}\left(n\right)$ denotes the number of partitions of $n$ into at most $k$ parts. See Table 26.9.1.

26.9.1		$p_{k}\left(n\right)=p\left(n\right),$
$k\geq n$ .
ⓘ Symbols: $p\left(\NVar{n}\right)$ : total number of partitions of $n$ , $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts, $k$ : nonnegative integer and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.9.E1 Encodings: TeX, pMML, png See also: Annotations for §26.9(i), §26.9 and Ch.26

Unrestricted partitions are covered in §27.14.

Table 26.9.1: Partitions

p_{k}\left(n\right)

$n$	$k$
$n$	0	1	2	3	4	5	6	7	8	9	10
0	1	1	1	1	1	1	1	1	1	1	1
1	0	1	1	1	1	1	1	1	1	1	1
2	0	1	2	2	2	2	2	2	2	2	2
3	0	1	2	3	3	3	3	3	3	3	3
4	0	1	3	4	5	5	5	5	5	5	5
5	0	1	3	5	6	7	7	7	7	7	7
6	0	1	4	7	9	10	11	11	11	11	11
7	0	1	4	8	11	13	14	15	15	15	15
8	0	1	5	10	15	18	20	21	22	22	22
9	0	1	5	12	18	23	26	28	29	30	30
10	0	1	6	14	23	30	35	38	40	41	42

ⓘ

Symbols:: $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts, $k$ : nonnegative integer and $n$ : nonnegative integer
Keywords:: restricted integer partitions, tables
Referenced by:: §26.9(i), §26.9(i)
Permalink:: http://dlmf.nist.gov/26.9.T1
See also:: Annotations for §26.9(i), §26.9 and Ch.26

A useful representation for a partition is the Ferrers graph in which the integers in the partition are each represented by a row of dots. An example is provided in Figure 26.9.1.

$\bullet$	$\bullet$	$\bullet$	$\bullet$	$\bullet$	$\bullet$	$\bullet$
$\bullet$	$\bullet$	$\bullet$	$\bullet$
$\bullet$	$\bullet$	$\bullet$
$\bullet$	$\bullet$	$\bullet$
$\bullet$	$\bullet$
$\bullet$

Figure 26.9.1: Ferrers graph of the partition

7+4+3+3+2+1

ⓘ

Referenced by:: §26.9(i), §26.9(i)
Permalink:: http://dlmf.nist.gov/26.9.F1
See also:: Annotations for §26.9(i), §26.9 and Ch.26

The conjugate partition is obtained by reflecting the Ferrers graph across the main diagonal or, equivalently, by representing each integer by a column of dots. The conjugate to the example in Figure 26.9.1 is $6+5+4+2+1+1+1$ . Conjugation establishes a one-to-one correspondence between partitions of $n$ into at most $k$ parts and partitions of $n$ into parts with largest part less than or equal to $k$ . It follows that $p_{k}\left(n\right)$ also equals the number of partitions of $n$ into parts that are less than or equal to $k$ .

$p_{k}\left(\leq m,n\right)$ is the number of partitions of $n$ into at most $k$ parts, each less than or equal to $m$ . It is also equal to the number of lattice paths from $(0,0)$ to $(m,k)$ that have exactly $n$ vertices $(h,j)$ , $1\leq h\leq m$ , $1\leq j\leq k$ , above and to the left of the lattice path. See Figure 26.9.2.

\begin{picture}(170.0,110.0)(-25.0,0.0)\put(0.0,0.0){\circle*{2.0}}\put(20.0,0%
.0){\circle*{2.0}}\put(40.0,0.0){\circle*{2.0}}\put(60.0,0.0){\circle*{2.0}}%
\put(80.0,0.0){\circle*{2.0}}\put(100.0,0.0){\circle*{2.0}}\put(120.0,0.0){%
\circle*{2.0}}
\put(0.0,20.0){\circle*{2.0}}\put(20.0,20.0){\circle*{2.0}}\put(40.0,20.0){%
\circle*{2.0}}\put(60.0,20.0){\circle*{2.0}}\put(80.0,20.0){\circle*{2.0}}\put%
(100.0,20.0){\circle*{2.0}}\put(120.0,20.0){\circle*{2.0}}
\put(0.0,40.0){\circle*{2.0}}\put(20.0,40.0){\circle*{2.0}}\put(40.0,40.0){%
\circle*{2.0}}\put(60.0,40.0){\circle*{2.0}}\put(80.0,40.0){\circle*{2.0}}\put%
(100.0,40.0){\circle*{2.0}}\put(120.0,40.0){\circle*{2.0}}
\put(0.0,60.0){\circle*{2.0}}\put(20.0,60.0){\circle*{2.0}}\put(40.0,60.0){%
\circle*{2.0}}\put(60.0,60.0){\circle*{2.0}}\put(80.0,60.0){\circle*{2.0}}\put%
(100.0,60.0){\circle*{2.0}}\put(120.0,60.0){\circle*{2.0}}
\put(0.0,80.0){\circle*{2.0}}\put(20.0,80.0){\circle*{2.0}}\put(40.0,80.0){%
\circle*{2.0}}\put(60.0,80.0){\circle*{2.0}}\put(80.0,80.0){\circle*{2.0}}\put%
(100.0,80.0){\circle*{2.0}}\put(120.0,80.0){\circle*{2.0}}
\put(0.0,100.0){\circle*{2.0}}\put(20.0,100.0){\circle*{2.0}}\put(40.0,100.0){%
\circle*{2.0}}\put(60.0,100.0){\circle*{2.0}}\put(80.0,100.0){\circle*{2.0}}%
\put(100.0,100.0){\circle*{2.0}}\put(120.0,100.0){\circle*{2.0}}
\put(0.0,0.0){\line(1,0){4.0}}\put(8.0,0.0){\line(1,0){4.0}}\put(16.0,0.0){%
\line(1,0){4.0}}\put(24.0,0.0){\line(1,0){4.0}}\put(32.0,0.0){\line(1,0){4.0}}%
\put(40.0,0.0){\line(1,0){4.0}}\put(48.0,0.0){\line(1,0){4.0}}\put(56.0,0.0){%
\line(1,0){4.0}}\put(64.0,0.0){\line(1,0){4.0}}\put(72.0,0.0){\line(1,0){4.0}}%
\put(80.0,0.0){\line(1,0){4.0}}\put(88.0,0.0){\line(1,0){4.0}}\put(96.0,0.0){%
\line(1,0){4.0}}\put(104.0,0.0){\line(1,0){4.0}}\put(112.0,0.0){\line(1,0){4.0%
}}
\put(0.0,20.0){\line(1,0){4.0}}\put(8.0,20.0){\line(1,0){4.0}}\put(16.0,20.0){%
\line(1,0){4.0}}\put(24.0,20.0){\line(1,0){4.0}}\put(32.0,20.0){\line(1,0){4.0%
}}\put(40.0,20.0){\line(1,0){4.0}}\put(48.0,20.0){\line(1,0){4.0}}\put(56.0,20%
.0){\line(1,0){4.0}}\put(64.0,20.0){\line(1,0){4.0}}\put(72.0,20.0){\line(1,0)%
{4.0}}\put(80.0,20.0){\line(1,0){4.0}}\put(88.0,20.0){\line(1,0){4.0}}\put(96.%
0,20.0){\line(1,0){4.0}}\put(104.0,20.0){\line(1,0){4.0}}\put(112.0,20.0){%
\line(1,0){4.0}}
\put(0.0,40.0){\line(1,0){4.0}}\put(8.0,40.0){\line(1,0){4.0}}\put(16.0,40.0){%
\line(1,0){4.0}}\put(24.0,40.0){\line(1,0){4.0}}\put(32.0,40.0){\line(1,0){4.0%
}}\put(40.0,40.0){\line(1,0){4.0}}\put(48.0,40.0){\line(1,0){4.0}}\put(56.0,40%
.0){\line(1,0){4.0}}\put(64.0,40.0){\line(1,0){4.0}}\put(72.0,40.0){\line(1,0)%
{4.0}}\put(80.0,40.0){\line(1,0){4.0}}\put(88.0,40.0){\line(1,0){4.0}}\put(96.%
0,40.0){\line(1,0){4.0}}\put(104.0,40.0){\line(1,0){4.0}}\put(112.0,40.0){%
\line(1,0){4.0}}
\put(0.0,60.0){\line(1,0){4.0}}\put(8.0,60.0){\line(1,0){4.0}}\put(16.0,60.0){%
\line(1,0){4.0}}\put(24.0,60.0){\line(1,0){4.0}}\put(32.0,60.0){\line(1,0){4.0%
}}\put(40.0,60.0){\line(1,0){4.0}}\put(48.0,60.0){\line(1,0){4.0}}\put(56.0,60%
.0){\line(1,0){4.0}}\put(64.0,60.0){\line(1,0){4.0}}\put(72.0,60.0){\line(1,0)%
{4.0}}\put(80.0,60.0){\line(1,0){4.0}}\put(88.0,60.0){\line(1,0){4.0}}\put(96.%
0,60.0){\line(1,0){4.0}}\put(104.0,60.0){\line(1,0){4.0}}\put(112.0,60.0){%
\line(1,0){4.0}}
\put(0.0,80.0){\line(1,0){4.0}}\put(8.0,80.0){\line(1,0){4.0}}\put(16.0,80.0){%
\line(1,0){4.0}}\put(24.0,80.0){\line(1,0){4.0}}\put(32.0,80.0){\line(1,0){4.0%
}}\put(40.0,80.0){\line(1,0){4.0}}\put(48.0,80.0){\line(1,0){4.0}}\put(56.0,80%
.0){\line(1,0){4.0}}\put(64.0,80.0){\line(1,0){4.0}}\put(72.0,80.0){\line(1,0)%
{4.0}}\put(80.0,80.0){\line(1,0){4.0}}\put(88.0,80.0){\line(1,0){4.0}}\put(96.%
0,80.0){\line(1,0){4.0}}\put(104.0,80.0){\line(1,0){4.0}}\put(112.0,80.0){%
\line(1,0){4.0}}
\put(0.0,100.0){\line(1,0){4.0}}\put(8.0,100.0){\line(1,0){4.0}}\put(16.0,100.%
0){\line(1,0){4.0}}\put(24.0,100.0){\line(1,0){4.0}}\put(32.0,100.0){\line(1,0%
){4.0}}\put(40.0,100.0){\line(1,0){4.0}}\put(48.0,100.0){\line(1,0){4.0}}\put(%
56.0,100.0){\line(1,0){4.0}}\put(64.0,100.0){\line(1,0){4.0}}\put(72.0,100.0){%
\line(1,0){4.0}}\put(80.0,100.0){\line(1,0){4.0}}\put(88.0,100.0){\line(1,0){4%
.0}}\put(96.0,100.0){\line(1,0){4.0}}\put(104.0,100.0){\line(1,0){4.0}}\put(11%
2.0,100.0){\line(1,0){4.0}}
\put(0.0,0.0){\line(0,1){4.0}}\put(0.0,8.0){\line(0,1){4.0}}\put(0.0,16.0){%
\line(0,1){4.0}}\put(0.0,24.0){\line(0,1){4.0}}\put(0.0,32.0){\line(0,1){4.0}}%
\put(0.0,40.0){\line(0,1){4.0}}\put(0.0,48.0){\line(0,1){4.0}}\put(0.0,56.0){%
\line(0,1){4.0}}\put(0.0,64.0){\line(0,1){4.0}}\put(0.0,72.0){\line(0,1){4.0}}%
\put(0.0,80.0){\line(0,1){4.0}}\put(0.0,88.0){\line(0,1){4.0}}\put(0.0,96.0){%
\line(0,1){4.0}}
\put(20.0,0.0){\line(0,1){4.0}}\put(20.0,8.0){\line(0,1){4.0}}\put(20.0,16.0){%
\line(0,1){4.0}}\put(20.0,24.0){\line(0,1){4.0}}\put(20.0,32.0){\line(0,1){4.0%
}}\put(20.0,40.0){\line(0,1){4.0}}\put(20.0,48.0){\line(0,1){4.0}}\put(20.0,56%
.0){\line(0,1){4.0}}\put(20.0,64.0){\line(0,1){4.0}}\put(20.0,72.0){\line(0,1)%
{4.0}}\put(20.0,80.0){\line(0,1){4.0}}\put(20.0,88.0){\line(0,1){4.0}}\put(20.%
0,96.0){\line(0,1){4.0}}
\put(40.0,0.0){\line(0,1){4.0}}\put(40.0,8.0){\line(0,1){4.0}}\put(40.0,16.0){%
\line(0,1){4.0}}\put(40.0,24.0){\line(0,1){4.0}}\put(40.0,32.0){\line(0,1){4.0%
}}\put(40.0,40.0){\line(0,1){4.0}}\put(40.0,48.0){\line(0,1){4.0}}\put(40.0,56%
.0){\line(0,1){4.0}}\put(40.0,64.0){\line(0,1){4.0}}\put(40.0,72.0){\line(0,1)%
{4.0}}\put(40.0,80.0){\line(0,1){4.0}}\put(40.0,88.0){\line(0,1){4.0}}\put(40.%
0,96.0){\line(0,1){4.0}}
\put(60.0,0.0){\line(0,1){4.0}}\put(60.0,8.0){\line(0,1){4.0}}\put(60.0,16.0){%
\line(0,1){4.0}}\put(60.0,24.0){\line(0,1){4.0}}\put(60.0,32.0){\line(0,1){4.0%
}}\put(60.0,40.0){\line(0,1){4.0}}\put(60.0,48.0){\line(0,1){4.0}}\put(60.0,56%
.0){\line(0,1){4.0}}\put(60.0,64.0){\line(0,1){4.0}}\put(60.0,72.0){\line(0,1)%
{4.0}}\put(60.0,80.0){\line(0,1){4.0}}\put(60.0,88.0){\line(0,1){4.0}}\put(60.%
0,96.0){\line(0,1){4.0}}
\put(80.0,0.0){\line(0,1){4.0}}\put(80.0,8.0){\line(0,1){4.0}}\put(80.0,16.0){%
\line(0,1){4.0}}\put(80.0,24.0){\line(0,1){4.0}}\put(80.0,32.0){\line(0,1){4.0%
}}\put(80.0,40.0){\line(0,1){4.0}}\put(80.0,48.0){\line(0,1){4.0}}\put(80.0,56%
.0){\line(0,1){4.0}}\put(80.0,64.0){\line(0,1){4.0}}\put(80.0,72.0){\line(0,1)%
{4.0}}\put(80.0,80.0){\line(0,1){4.0}}\put(80.0,88.0){\line(0,1){4.0}}\put(80.%
0,96.0){\line(0,1){4.0}}
\put(100.0,0.0){\line(0,1){4.0}}\put(100.0,8.0){\line(0,1){4.0}}\put(100.0,16.%
0){\line(0,1){4.0}}\put(100.0,24.0){\line(0,1){4.0}}\put(100.0,32.0){\line(0,1%
){4.0}}\put(100.0,40.0){\line(0,1){4.0}}\put(100.0,48.0){\line(0,1){4.0}}\put(%
100.0,56.0){\line(0,1){4.0}}\put(100.0,64.0){\line(0,1){4.0}}\put(100.0,72.0){%
\line(0,1){4.0}}\put(100.0,80.0){\line(0,1){4.0}}\put(100.0,88.0){\line(0,1){4%
.0}}\put(100.0,96.0){\line(0,1){4.0}}
\put(120.0,0.0){\line(0,1){4.0}}\put(120.0,8.0){\line(0,1){4.0}}\put(120.0,16.%
0){\line(0,1){4.0}}\put(120.0,24.0){\line(0,1){4.0}}\put(120.0,32.0){\line(0,1%
){4.0}}\put(120.0,40.0){\line(0,1){4.0}}\put(120.0,48.0){\line(0,1){4.0}}\put(%
120.0,56.0){\line(0,1){4.0}}\put(120.0,64.0){\line(0,1){4.0}}\put(120.0,72.0){%
\line(0,1){4.0}}\put(120.0,80.0){\line(0,1){4.0}}\put(120.0,88.0){\line(0,1){4%
.0}}\put(120.0,96.0){\line(0,1){4.0}}
\put(-28.0,0.0){$(0,0)$}
\put(125.0,100.0){$(6,5)$}
\put(0.0,0.0){\line(0,1){20.0}}
\put(0.0,20.0){\line(1,0){40.0}}
\put(40.0,20.0){\line(0,1){20.0}}
\put(40.0,40.0){\line(1,0){20.0}}
\put(60.0,40.0){\line(0,1){20.0}}
\put(60.0,60.0){\line(1,0){40.0}}
\put(100.0,60.0){\line(0,1){40.0}}
\put(100.0,100.0){\line(1,0){20.0}}
\put(0.0,100.0){\circle*{5.0}}\put(20.0,100.0){\circle*{5.0}}\put(40.0,100.0){%
\circle*{5.0}}\put(60.0,100.0){\circle*{5.0}}\put(80.0,100.0){\circle*{5.0}}
\put(0.0,80.0){\circle*{5.0}}\put(20.0,80.0){\circle*{5.0}}\put(40.0,80.0){%
\circle*{5.0}}\put(60.0,80.0){\circle*{5.0}}\put(80.0,80.0){\circle*{5.0}}
\put(0.0,60.0){\circle*{5.0}}\put(20.0,60.0){\circle*{5.0}}\put(40.0,60.0){%
\circle*{5.0}}
\put(0.0,40.0){\circle*{5.0}}\put(20.0,40.0){\circle*{5.0}}
\end{picture} — Figure 26.9.2: The partition $5+5+3+2$ represented as a lattice path. Magnify

Equations (26.9.2)–(26.9.3) are examples of closed forms that can be computed explicitly for any positive integer $k$ . See Andrews (1976, p. 81).

26.9.2		$p_{0}\left(n\right)=0,$
$n>0$ ,
ⓘ Symbols: $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts and $n$ : nonnegative integer Referenced by: §26.9(i) Permalink: http://dlmf.nist.gov/26.9.E2 Encodings: TeX, pMML, png See also: Annotations for §26.9(i), §26.9 and Ch.26

26.9.3	$\displaystyle p_{1}\left(n\right)$	$\displaystyle=1,$
	$\displaystyle p_{2}\left(n\right)$	$\displaystyle=1+\left\lfloor n/2\right\rfloor,$
	$\displaystyle p_{3}\left(n\right)$	$\displaystyle=1+\left\lfloor\frac{n^{2}+6n}{12}\right\rfloor.$
ⓘ Symbols: $\left\lfloor\NVar{x}\right\rfloor$ : floor of $x$ , $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts and $n$ : nonnegative integer Referenced by: §26.9(i) Permalink: http://dlmf.nist.gov/26.9.E3 Encodings: TeX, TeX, TeX, pMML, pMML, pMML, png, png, png See also: Annotations for §26.9(i), §26.9 and Ch.26

§26.9(ii) Generating Functions

ⓘ

Keywords:: Gaussian polynomials, definition, generating functions, $q$ -binomial coefficient, restricted integer partitions
Notes:: See Andrews (1976, pp. 36, 47).
Referenced by:: §17.2(iii), §17.2(iii), §26.16
Permalink:: http://dlmf.nist.gov/26.9.ii
See also:: Annotations for §26.9 and Ch.26

In what follows

26.9.4		$\genfrac{[}{]}{0.0pt}{}{m}{n}_{q}=\prod_{j=1}^{n}\frac{1-q^{m-n+j}}{1-q^{j}},$
$n\geq 0$ ,
ⓘ Symbols: $\genfrac{[}{]}{0.0pt}{}{\NVar{n}}{\NVar{m}}_{\NVar{q}}$ : $q$ -binomial coefficient (or Gaussian polynomial), $j$ : nonnegative integer, $m$ : nonnegative integer, $n$ : nonnegative integer and $q$ : parameter Permalink: http://dlmf.nist.gov/26.9.E4 Encodings: TeX, pMML, png See also: Annotations for §26.9(ii), §26.9 and Ch.26

is the Gaussian polynomial (or $q$ -binomial coefficient); see also §§17.2(i)–17.2(ii). In the present chapter $m\geq n\geq 0$ in all cases. It is also assumed everywhere that $|q|<1$ .

26.9.5		$\sum_{n=0}^{\infty}p_{k}\left(n\right)q^{n}=\prod_{j=1}^{k}\frac{1}{1-q^{j}}=1% +\sum_{m=1}^{\infty}\genfrac{[}{]}{0.0pt}{}{k+m-1}{m}_{q}q^{m},$
ⓘ Symbols: $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts, $\genfrac{[}{]}{0.0pt}{}{\NVar{n}}{\NVar{m}}_{\NVar{q}}$ : $q$ -binomial coefficient (or Gaussian polynomial), $j$ : nonnegative integer, $k$ : nonnegative integer, $m$ : nonnegative integer, $n$ : nonnegative integer and $q$ : parameter Permalink: http://dlmf.nist.gov/26.9.E5 Encodings: TeX, pMML, png See also: Annotations for §26.9(ii), §26.9 and Ch.26

26.9.6		$\sum_{n=0}^{\infty}p_{k}\left(\leq m,n\right)q^{n}=\genfrac{[}{]}{0.0pt}{}{m+k% }{k}_{q}.$
ⓘ Symbols: $\genfrac{[}{]}{0.0pt}{}{\NVar{n}}{\NVar{m}}_{\NVar{q}}$ : $q$ -binomial coefficient (or Gaussian polynomial), $p_{\NVar{k}}\left(\leq\NVar{m},\NVar{n}\right)$ : number of partitions of $n$ into at most $k$ parts, each less than or equal to $m$ , $k$ : nonnegative integer, $m$ : nonnegative integer, $n$ : nonnegative integer and $q$ : parameter Permalink: http://dlmf.nist.gov/26.9.E6 Encodings: TeX, pMML, png See also: Annotations for §26.9(ii), §26.9 and Ch.26

Also, when $|xq|<1$

26.9.7		$\sum_{m,n=0}^{\infty}p_{k}\left(\leq m,n\right)x^{k}q^{n}=1+\sum_{k=1}^{\infty% }\genfrac{[}{]}{0.0pt}{}{m+k}{k}_{q}x^{k}=\prod_{j=0}^{m}\frac{1}{1-x\,q^{j}}.$
ⓘ Symbols: $\genfrac{[}{]}{0.0pt}{}{\NVar{n}}{\NVar{m}}_{\NVar{q}}$ : $q$ -binomial coefficient (or Gaussian polynomial), $p_{\NVar{k}}\left(\leq\NVar{m},\NVar{n}\right)$ : number of partitions of $n$ into at most $k$ parts, each less than or equal to $m$ , $x$ : real variable, $j$ : nonnegative integer, $k$ : nonnegative integer, $m$ : nonnegative integer, $n$ : nonnegative integer and $q$ : parameter Permalink: http://dlmf.nist.gov/26.9.E7 Encodings: TeX, pMML, png See also: Annotations for §26.9(ii), §26.9 and Ch.26

§26.9(iii) Recurrence Relations

ⓘ

Keywords:: recurrence relations, restricted integer partitions
Notes:: (26.9.9) is a special case of equation (2.23) in Bressoud (1999, p. 60).
Permalink:: http://dlmf.nist.gov/26.9.iii
See also:: Annotations for §26.9 and Ch.26

26.9.8		$p_{k}\left(n\right)=p_{k}\left(n-k\right)+p_{k-1}\left(n\right);$
ⓘ Symbols: $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts, $k$ : nonnegative integer and $n$ : nonnegative integer Referenced by: §26.10(iii) Permalink: http://dlmf.nist.gov/26.9.E8 Encodings: TeX, pMML, png See also: Annotations for §26.9(iii), §26.9 and Ch.26

equivalently, partitions into at most $k$ parts either have exactly $k$ parts, in which case we can subtract one from each part, or they have strictly fewer than $k$ parts.

26.9.9		$p_{k}\left(n\right)=\frac{1}{n}\sum_{t=1}^{n}p_{k}\left(n-t\right)\sum_{\begin% {subarray}{c}j\mathbin{\|}t\\ j\leq k\end{subarray}}j,$
ⓘ Symbols: $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts, $j$ : nonnegative integer, $k$ : nonnegative integer and $n$ : nonnegative integer Referenced by: §26.9(iii) Permalink: http://dlmf.nist.gov/26.9.E9 Encodings: TeX, pMML, png See also: Annotations for §26.9(iii), §26.9 and Ch.26

where the inner sum is taken over all positive divisors of $t$ that are less than or equal to $k$ .

§26.9(iv) Limiting Form

ⓘ

Keywords:: limiting form, restricted integer partitions
Notes:: See Andrews (1976, Chapter 6).
Permalink:: http://dlmf.nist.gov/26.9.iv
See also:: Annotations for §26.9 and Ch.26

As $n\to\infty$ with $k$ fixed,

26.9.10		$p_{k}\left(n\right)\sim\frac{n^{k-1}}{k!(k-1)!}.$
ⓘ Symbols: $\sim$ : asymptotic equality, $!$ : factorial (as in $n!$ ), $p_{\NVar{k}}\left(\NVar{n}\right)$ : total number of partitions of $n$ into at most $k$ parts, $k$ : nonnegative integer and $n$ : nonnegative integer Permalink: http://dlmf.nist.gov/26.9.E10 Encodings: TeX, pMML, png See also: Annotations for §26.9(iv), §26.9 and Ch.26

26.8 Set Partitions: Stirling Numbers 26.10 Integer Partitions: Other Restrictions

Site Privacy Accessibility Privacy Program Copyrights Vulnerability Disclosure No Fear Act Policy FOIA Environmental Policy Scientific Integrity Information Quality Standards Commerce.gov Science.gov USA.gov

§26.9 Integer Partitions: Restricted Number and Part Size

Contents

§26.9(i) Definitions

§26.9(ii) Generating Functions

§26.9(iii) Recurrence Relations

§26.9(iv) Limiting Form

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!

$n$	$k$
$n$	0	1	2	3	4	5	6	7	8	9	10
0	1	1	1	1	1	1	1	1	1	1	1
1	0	1	1	1	1	1	1	1	1	1	1
2	0	1	2	2	2	2	2	2	2	2	2
3	0	1	2	3	3	3	3	3	3	3	3
4	0	1	3	4	5	5	5	5	5	5	5
5	0	1	3	5	6	7	7	7	7	7	7
6	0	1	4	7	9	10	11	11	11	11	11
7	0	1	4	8	11	13	14	15	15	15	15
8	0	1	5	10	15	18	20	21	22	22	22
9	0	1	5	12	18	23	26	28	29	30	30
10	0	1	6	14	23	30	35	38	40	41	42

$n$	$k$
$n$	0	1	2	3	4	5	6	7	8	9	10
0	1	1	1	1	1	1	1	1	1	1	1
1	0	1	1	1	1	1	1	1	1	1	1
2	0	1	2	2	2	2	2	2	2	2	2
3	0	1	2	3	3	3	3	3	3	3	3
4	0	1	3	4	5	5	5	5	5	5	5
5	0	1	3	5	6	7	7	7	7	7	7
6	0	1	4	7	9	10	11	11	11	11	11
7	0	1	4	8	11	13	14	15	15	15	15
8	0	1	5	10	15	18	20	21	22	22	22
9	0	1	5	12	18	23	26	28	29	30	30
10	0	1	6	14	23	30	35	38	40	41	42

$n$	$k$
$n$	0	1	2	3	4	5	6	7	8	9	10
0	1	1	1	1	1	1	1	1	1	1	1
1	0	1	1	1	1	1	1	1	1	1	1
2	0	1	2	2	2	2	2	2	2	2	2
3	0	1	2	3	3	3	3	3	3	3	3
4	0	1	3	4	5	5	5	5	5	5	5
5	0	1	3	5	6	7	7	7	7	7	7
6	0	1	4	7	9	10	11	11	11	11	11
7	0	1	4	8	11	13	14	15	15	15	15
8	0	1	5	10	15	18	20	21	22	22	22
9	0	1	5	12	18	23	26	28	29	30	30
10	0	1	6	14	23	30	35	38	40	41	42