§ 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:
- [5 ]
- [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 parts decreases 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 keeping the same number of parts.