26 Combinatorial AnalysisProperties26.8 Set Partitions: Stirling Numbers26.10 Integer Partitions: Other Restrictions

- §26.9(i) Definitions
- §26.9(ii) Generating Functions
- §26.9(iii) Recurrence Relations
- §26.9(iv) Limiting Form

${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\ge n$. | |||

Unrestricted partitions are covered in §27.14.

$n$ | $k$ | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

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 |

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

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}(\le m,n)$ 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\le h\le m$, $1\le j\le 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$, | |||

26.9.3 | ${p}_{1}\left(n\right)$ | $=1,$ | ||

${p}_{2}\left(n\right)$ | $=1+\lfloor n/2\rfloor ,$ | |||

${p}_{3}\left(n\right)$ | $=1+\lfloor {\displaystyle \frac{{n}^{2}+6n}{12}}\rfloor .$ | |||

In what follows

26.9.4 | $${\left[\genfrac{}{}{0.0pt}{}{m}{n}\right]}_{q}=\prod _{j=1}^{n}\frac{1-{q}^{m-n+j}}{1-{q}^{j}},$$ | ||

$n\ge 0$, | |||

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

26.9.5 | $$\sum _{n=0}^{\mathrm{\infty}}{p}_{k}\left(n\right){q}^{n}=\prod _{j=1}^{k}\frac{1}{1-{q}^{j}}=1+\sum _{m=1}^{\mathrm{\infty}}{\left[\genfrac{}{}{0.0pt}{}{k+m-1}{m}\right]}_{q}{q}^{m},$$ | ||

26.9.6 | $$\sum _{n=0}^{\mathrm{\infty}}{p}_{k}(\le m,n){q}^{n}={\left[\genfrac{}{}{0.0pt}{}{m+k}{k}\right]}_{q}.$$ | ||

Also, when $$

26.9.7 | $$\sum _{m,n=0}^{\mathrm{\infty}}{p}_{k}(\le m,n){x}^{k}{q}^{n}=1+\sum _{k=1}^{\mathrm{\infty}}{\left[\genfrac{}{}{0.0pt}{}{m+k}{k}\right]}_{q}{x}^{k}=\prod _{j=0}^{m}\frac{1}{1-x{q}^{j}}.$$ | ||

26.9.8 | $${p}_{k}\left(n\right)={p}_{k}\left(n-k\right)+{p}_{k-1}\left(n\right);$$ | ||

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{array}{c}j|t\\ j\le k\end{array}}j,$$ | ||

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

As $n\to \mathrm{\infty}$ with $k$ fixed,

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