Integer Partitions

A partition of an integer \(N\) is a list of numbers, typically written in decreasing order, that add up to \(N\). For instance, the complete list of partitions of 6 would be: \[ (6), (5, 1), (4, 2), (4, 1, 1), (3, 3), (3, 2, 1), (3, 1, 1, 1), (2, 2, 2), (2, 2, 1, 1), (2, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1) \]
We may also be interested in restricted partitions. In some cases, we may require the partition to have a minimum or maximum (or both) number of parts. For instance, the partitions of 6 with exactly three parts are: \[ (4, 1, 1), (3, 2, 1), (2, 2, 2) \] Other times, we may need partitions with maximum or minimum values, meaning each part of the partition is restricted. The partitions of 6 with parts at least 2 and at most 5 are \[ (4, 2), (3, 3), (2, 2, 2) \] Finally, we may need partitions whose parts are all even or all odd, or whose parts are distinct (that is, no two parts are equal).

Each partition of an integer can be expressed with a picture called a Young diagram. These diagrams are characterized by a collection of boxes arranged in rows, so that the rows weakly decrease in length from top to bottom and the columns weakly decrease from left to right. Listing the length of each row gives an integer partition of \(N\) if the diagram contains \(N\) boxes.

Ferrer's graphs are similar to Young diagrams, using filled circles instead of boxes.