§ Integer partitions: Recurrence

An integer partition of an integer nn is a sequence of numbers p[1],p[2],p[n]p[1], p[2], \dots p[n] which is weakly decreasing: so we have p[1]p[2]p[n]p[1] \geq p[2] \dots \geq p[n]. For example, these are the integer partitions of 55:
  • [5]
  • [4, 1]
  • [3, 2]
  • [3, 1, 1]
  • [2, 2, 1]
  • [2, 1, 1, 1]
  • [1, 1, 1, 1, 1]
Thus, P(5)=7P(5) = 7. We denote by P(n,k)P(n, k) the number of partitions of nn into kk parts. So we have P(5,1)=1P(5, 1) = 1, P(5,2)=2P(5, 2) = 2, P(5,3)=2P(5, 3) = 2, P(5,4)=1P(5, 4) = 1, P(5,5)=1P(5, 5) = 1. The recurrence for partitions is:
P(n,k)=P(n1,k1)+P(nk,k)P(n, k) = P(n-1, k-1) + P(n-k, k)
The idea is to consider a partition p[1],p[2],,p[k]p[1], p[2], \dots, p[k] of nn based on the final element:
  • if p[k]=1p[k] = 1, then we get a smaller partition by removing the kkth part, giving us a partition of (n1)(n-1) as [p[1],p[2],,p[k1]][p[1], p[2], \dots, p[k-1]]. Here the number decreases from n(n1)n \mapsto (n-1) and the number of partsdecreases from k(k1)k \mapsto (k-1).
  • if p[k]1p[k] \neq 1 (that is, p[k]>1p[k] > 1), then we get a partition of nkn-k by knocking off a 11 from each partition, giving us[p[1]1,p[2]1,,p[k]1][p[1] - 1, p[2] - 1, \dots, p[k]-1]. Here we decrement on the number nnkn \mapsto n - k while still keepingthe same number of parts.

§ References