In the number theory of integer partitions, the numbers ${\displaystyle p_{k}(n)}$ denote both the number of partitions of ${\displaystyle n}$ into exactly ${\displaystyle k}$ parts (that is, sums of ${\displaystyle k}$ positive integers that add to ${\displaystyle n}$), and the number of partitions of ${\displaystyle n}$ into parts of maximum size exactly ${\displaystyle k}$. These two types of partition are in bijection with each other, by a diagonal reflection of their Young diagrams. Their numbers can be arranged into a triangle, the triangle of partition numbers, in which the ${\displaystyle n}$th row gives the partition numbers ${\displaystyle p_{1}(n),p_{2}(n),\dots ,p_{n}(n)}$:^[1]

Recurrence relation

Analogously to Pascal's triangle, these numbers may be calculated using the recurrence relation^[2]

$${\displaystyle p_{k}(n)=p_{k-1}(n-1)+p_{k}(n-k).}$$

As base cases, ${\displaystyle p_{1}(1)=1}$, and any value on the right hand side of the recurrence that would be outside the triangle can be taken as zero. This equation can be explained by noting that each partition of ${\displaystyle n}$ into ${\displaystyle k}$ pieces, counted by ${\displaystyle p_{k}(n)}$, can be formed either by adding a piece of size one to a partition of ${\displaystyle n-1}$ into ${\displaystyle k-1}$ pieces, counted by ${\displaystyle p_{k-1}(n-1)}$, or by increasing by one each piece in a partition of ${\displaystyle n-k}$ into ${\displaystyle k}$ pieces, counted by ${\displaystyle p_{k}(n-k)}$.

Row sums and diagonals

In the triangle of partition numbers, the sum of the numbers in the ${\displaystyle n}$th row is the partition number ${\displaystyle p(n)}$. These numbers form the sequence

omitting the initial value ${\displaystyle p(0)=1}$ of the partition numbers. Each diagonal from upper left to lower right is eventually constant, with the constant parts of these diagonals extending approximately from halfway across each row to its end. The values of these constants are the partition numbers 1, 1, 2, 3, 5, 7, ... again.^[3]

References