# §26.9 Integer Partitions: Restricted Number and Part Size

## §26.9(i) Definitions

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

Unrestricted partitions are covered in §27.14.

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.

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.

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

## §26.9(ii) Generating Functions

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

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},$
 26.9.6 $\sum_{n=0}^{\infty}p_{k}\left(\leq m,n\right)q^{n}=\genfrac{[}{]}{0.0pt}{}{m+k% }{k}_{q}.$

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

## §26.9(iii) Recurrence Relations

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

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

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

 26.9.10 $p_{k}\left(n\right)\sim\frac{n^{k-1}}{k!(k-1)!}.$