It’s Time for a Breakdown (of Numbers)

Now it’s time for a breakdown… (cue En Vogue’s My Lovin’ (You’re Never Gonna Get It))

In particular, a breakdown of numbers! Today we’ll be talking about partitions of numbers. At first glance, they’re a fairly simple concept: a partition of a positive number n is a way to break it up into a sum of positive integers. For example, the partitions of 5 are 1+1+1+1+1, 2+1+1+1, 2+2+1, 3+1+1, 3+2, 4+1, and 5, for a total of 7 partitions. Note that 5 still counts as a partition of 5. Also, notice the order of the numbers in the sum doesn’t matter: 5 = 2+3 is considered the same as 5 = 3+2, so we don’t count it twice.

It can get a little tiring looking at long sums of numbers, so we can instead represent these partitions with fun graphs! The most common types are Ferrers diagrams and Young diagrams. To be honest, there’s not a huge difference between them, unless you are really passionate about distinguishing dots and boxes.

Some brief history: Ferrers diagrams are named after British mathematician Norman Ferrers. You may also be thinking of the fantastic chocolate delight, Ferrero Rocher…okay maybe not, but I am now. However, these are not related (as far as I know), but funnily enough the diagrams look like lines of these heavenly chocolate balls. Per usual, the best way to demonstrate is with a picture:

For n =15, one partition is 6+3+3+2+1, which is ordered from the largest to smallest parts (the numbers in the sum). Each row is the size of a part in the partition.

(See what I mean about the Rochers?!) Here’s another example– these are all the 5 partitions of the number 4 represented as Ferrers diagrams (image taken from Wikipedia):

Now let’s quickly touch on Young diagrams, which work the same way as Ferrers diagrams (at least in the conventions we’re using). Young diagrams were named after another British mathematician Alfred Young (the Brits are really killing the partition game!), but uses boxes instead of dots. Here’s an example: the same 5 partitions of the number 4 represented as Young diagrams this time,

While this difference seems irrelevant, these Young diagrams can be modified into something called Young tableaux (by filling the currently empty boxes with numbers), which are very significant in the study of symmetric polynomials and group representation theory!

Though they aren’t the most complicated, these diagrams are handy, and can really simplify some proofs (and also tie into generating functions quite nicely). I would give some examples, but unfortunately this article can only be so long. But look out for a future column that elaborates on this!

Now, an interesting question naturally arises: how many partitions of a given number n are there? Although it seems rather simple, answering it is unfortunately not. To look closer at this question, let p(n) be the number of partitions of n. For example, we’ve seen that p(4) = 5, as 4 has 5 partitions. Using this function, we get a sequence: p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, p(6) = 11, p(7) = 15, p(8) = 22, p(9) = 30, p(10) = 42, …

We can see that this function is growing faster and faster. In fact, p(100) is over 190 million! To be exact, 100 has 190,569,292 partitions. Yikes. Clearly, this function becomes really hard to compute as n grows larger.

So are these numbers totally unpredictable? Are we never gonna get it? Is it time for an actual break down? No, no, and no! To console you, let me bring you back to the story of the brilliant Indian mathematician, Srinivasa Ramanujan. He had an uncanny ability to see fantastical patterns in places no one else would think to look. He studied this partition function, and came up with three famous congruences for it in 1919.

The first congruence is that, for nonnegative integers k, p(5k+4) is divisible by 5. What does this mean? Well first, numbers of the form 5k+4 are numbers that end in 4 or 9. For example, for k=0, 5k+4 = 4; for k=1, 5k+4 = 9, for k=2, 5k+4 = 14, and so on. Then,

and so on. As you can see, 5, 30, and 135 are all divisible by 5, hooray!

Similarly, the second congruence is, for nonnegative integers k, p(7k+5) is divisible by 7. For example,

and so on. And indeed, 7, 77, and 490 are all divisible by 7.

Finally, the third congruence is, for nonnegative integers k, p(11k+6) is divisible by 11. For example,

and so on. As we expected, 11, 297, and 3718 are all divisible by 11– that’s three for three!

Following this pattern, one might expect that p(13k+7) is divisible by 13…nope. Sorry! But, your next (completely natural and obvious) guess, that p(17303k + 237) is divisible by 13, is absolutely correct! Joking aside, this bizarre result was found around 50 years later by (yet another!) British mathematician Dr. A. O. L. Atkin. So we have congruences like this for primes (numbers that are divisible by only one and themself) 5, 7, 11, and 13. What about the rest of the primes? Turns out that there are similar Ramanujan congruences for every prime greater than three! This was proved in 2000 by Japanese-American mathematician Dr. Ken Ono (who I actually researched under at the 2020 UVa REU summer program! Let me tell you– he’s super awesome.) The year after, in 2001, he and Dr. Scott Ahlgren went even further and proved that these congruences exist for every number relatively prime to 6, i.e. every number that isn’t divisible by 2 or 3. Needless to say, that is a lot of numbers, and a mind-blowing result!

So we’ve seen that these numbers are not at all totally unpredictable and that we should hold off on a breakdown for now. Now, back to our original question: how many partitions of a number n are there? Well, currently we don’t have an exact easy formula that outputs the exact number of partitions of n. However, there are approximations (in particular, asymptotics) that tell us how the function behaves, as well as recurrence relations for which we can use to calculate some values of p(n) exactly.

Okay, and? Why do we care about partitions? Well, if you must have ‘applications,’ partitions are used in many, many areas. Of course, they are used in lots of pure math (as mentioned above), like in studying symmetric polynomials. But they’re also used in the mathematics of shuffling (which does make some sense as you are breaking apart a fixed number of cards). Perhaps surprisingly, partitions also make an appearance in genetics, like in Ewen’s sampling formula, and in statistical mechanics (both classical and quantum)! One major example is the equipartition theorem, which can be thought of as “shuffling energies,” which is something you’ve definitely thought about if you’ve taken physics. Hence, understanding this partition function is incredibly useful across STEM!

And so it seems we have, in fact, gotten it, my lovin’ ;) (a contradiction to En Vogue’s anthem). Now I’m going to go make some Ferrers diagrams out of Ferrero Rochers (and subsequently eat them).

Until next time! If you found this interesting, make sure to check out the next column! If you have any questions or comments, please email me at apoorvapwrites@gmail.com.

To be the first one to hear about all my new articles, recent events, and latest projects, make sure to subscribe to my newsletter: Letter? I Hardly Know Her!