§ Integer partitions: Recurrence

An integer partition of an integer $n$ is a sequence of numbers $p[1], p[2], \dots p[n]$ which is weakly decreasing: so we have $p[1] \geq p[2] \dots \geq p[n]$. For example, these are the integer partitions of $5$:

• [5 ]
• [4, 1 ]
• [3, 2 ]
• [3, 1, 1 ]
• [2, 2, 1 ]
• [2, 1, 1, 1 ]
• [1, 1, 1, 1, 1 ]

Thus, $P(5) = 7$. We denote by $P(n, k)$ the number of partitions of $n$ into $k$ parts. So we have $P(5, 1) = 1$, $P(5, 2) = 2$, $P(5, 3) = 2$, $P(5, 4) = 1$, $P(5, 5) = 1$.
The recurrence for partitions is:

The idea is to consider a partition $p[1], p[2], \dots, p[k]$ of $n$ based on the final element:

• if $p[k] = 1$, then we get a smaller partition by removing the $k$th part, giving us a partition of $(n-1)$as $[p[1], p[2], \dots, p[k-1]]$. Here the number decreases from $n \mapsto (n-1)$ and the number of parts decreases from $k \mapsto (k-1)$.
• if $p[k] \neq 1$ (that is, $p[k] > 1$), then we get a partition of $n-k$ by knocking off a $1$ from each partition, giving us $[p[1] - 1, p[2] - 1, \dots, p[k]-1]$. Here we decrement on the number $n \mapsto n - k$ while still keeping the same number of parts.

§ References

• Bijective Combinatorics
• Slides by Brian Miceli