A Universe of Sorts

§ 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

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:

P(n, k) = P(n-1, k-1) + P(n-k, k)

The idea is to consider a partition

p[1], p[2], \dots, p[k]

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.