
The partitions of 4 are listed below:
The partitions of 8 are listed below:
The partition 6 + 4 + 3 + 1 of the positive number 14 can be represented by the following graph:
o o o o o o o o o o o o o o
6+4+3+1The 14 circles are lined up in 4 columns, each having the size of a part of the partition. The graphs for the 5 partitions of the number 4 are listed below:
o o o o o o o o o o o o o o o o o o o o
4 3+1 2+2 2+1+1 1+1+1+1If we now flip the graph of the partition 6 + 4 + 3 + 1 along the NWSE axis, we obtain another partition of 14:
o o o o o o o o o o o o o o o o o o o o > o o o o o o o o
6+4+3+1 4+3+3+2+1+1By turning the rows into columns, we obtain the partition 4 + 3 + 3 + 2 + 1 + 1 of the number 14. Such partitions are said to be conjugate of one another. In the case of the number 4, partitions 4 and 1 + 1 + 1 + 1 are conjugate pairs, and partitions 3 + 1 and 2 + 1 + 1 are conjugate of each other. Of particular interest is the partition 2 + 2, which has itself as conjugate. Such a paritition is said to be selfconjugate.
Claim: The number of selfconjugate partitions is the same as the number of partitions with distinct odd parts.
Proof (sketch): The crucial observation is that every odd part can be "folded" in the middle to form a self conjugate graph:
o o o > o o o o o o oOne can then obtain a bijection between the set of partitions with distinct odd parts and the set of selfconjugate partitions, as illustrated by the following example:
o * x o o o o o o * x o * * * * o * x <> o * x x o * o * x o * o * o * o * o o
9+7+3 5+5+4+3+2 distinct odd selfconjugate
Similar techniques can be employed to establish, for example, the following equalities:
The number of partitions of a positive integer n is given by the Partition function p(n). The number of partitions of n into exactly k parts is denoted by p_{k}(n).
Ferrers graph techniques also allow us to prove results like the following:
Elementary introduction to the topic of integer partition, including discussion of Ferrers graph, can be found in the following reference:
Search Encyclopedia

Featured Article
