§ Integer partitions: Recurrence
An integer partition of an integer is a sequence of numbers which
is weakly decreasing: so we have . For example, these
are the integer partitions of :
Thus, . We denote by the number of partitions of into parts.
So we have , , , , .
The recurrence for partitions is:
- [4, 1]
- [3, 2]
- [3, 1, 1]
- [2, 2, 1]
- [2, 1, 1, 1]
- [1, 1, 1, 1, 1]
The idea is to consider a partition of based on the final element:
- if , then we get a smaller partition by removing the th part, giving us a partition of as . Here the number decreases from and the number of partsdecreases from .
- if (that is, ), then we get a partition of by knocking off a from each partition, giving us. Here we decrement on the number while still keepingthe same number of parts.