Partitions

By Sean Malcolm, Monash University

A partition of a number is a way of breaking a number into a sum. For example, a partition of 7 is 1+3+4, a partition of 19 is 10+5+9, and so on. An obvious question to ask is how many partitions there are of a given number. For instance, the number 4 has five partitions: 4, 3+1, 2+2, 2+1+1 and 1+1+1+1. The sequence of the number of partitions of n is 1,1,2,3,5,7,11,15,22,30…

One way to visualize partitions is to imagine blocks arranged into columns called young diagrams. Suppose we want to visualize the partition 11=5+3+2+1. We imagine a column of 5 blocks, and to its right a column of 3 blocks, then a column of 2 blocks, and then lastly a column consisting of only one block. Adding up the number of blocks in each column gives 11. Such an arrangement of blocks is called a young diagram, and are useful objects in the study of partitions, as we shall see.

One variation on the idea of partitions comes from limiting the size of the largest part of the partition. For example, as we saw above there are five partitions of 4, but only three of which contain no part greater than 2. This can be visualised with young diagrams as well, by limiting the height of the columns.

Another variation is limiting the number of parts in a partition. For example, there are only three partitions of 4 that contain no more than 2 parts. This can be visualised by limiting the total number of columns we can add to the young diagrams, or by restricting the row size of the young diagrams.

Notice that the number of partitions of 4 into at most 2 parts was the same number of partitions of 4 where the largest part is 2. This is not a coincidence, and surprisingly is true in general! For any number n, the number partitions of n into at most p parts is equal to the number of partitions of n where the largest part is p. While it may seem like a difficult task to show that this is true, the proof is remarkably simple if we leverage the concept of the young diagrams.

Consider some young diagram representing some partition of n. Now draw a line north-east through the corner square, and imagine flipping the young diagram over this line, so the columns become the rows. This new young diagram is called the conjugate, and its columns are the parts of potentially different partition of n. Note that there is by definition a one-to-one correspondence between the young diagrams of a partition and the conjugate diagrams.

Now let n be arbitrary. Consider every partition of n into at most p parts and their associated young diagrams. Remember this means that the young diagrams consist of at most n columns. Now take all of these young diagrams and take their conjugates. Since the rows and columns have swapped, the longest column is the length of the longest row before the conjugation, but the longest row can’t be longer than the number of columns which is p. Thus the columns of the conjugate diagrams can’t be taller than p. But then these conjugate diagrams correspond to the partitions of n in which the largest part is not greater than p. And since there is a one-to-one correspondence, there must be the same number.

Sean Malcolm was one of the recipients of a 2017/18 AMSI Vacation Research Scholarship.

Contact Us

We're not around right now. But you can send us an email and we'll get back to you, asap.

Not readable? Change text.