I’ve recently been revisiting Euler’s Theorem. Not that one. No, not the one on this commemorative stamp either. No, no, not the totient function one. (Good guess though.)
I mean the one about partitions.
What is a partition? It’s simply a way of splitting up a number (a positive integer) into smaller pieces. For instance 2+2+1 is a partition of 5. The question is: how many ways of doing this are there?
Well there’s just one partition of one, namely 1.
There are 2 partitions of two: 2 and 1+1.
There are the 3 partitions of three: 3, 2+1, 1+1+1. (Notice that for these purposes, we count 2+1 and 1+2 as the same partition.)
So far the pattern looks rather easy. But there are the 5 partitions of four:
4, 3+1, 2+2, 2+1+1, 1+1+1+1
And then 7 partitions of five:
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+, 1+1+1+1+1
Continuing the sequence, we find 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010,…
What’s the pattern now? Finding an explicit formula for the number of partitions of is seriously hard. Even Euler couldn’t manage it. But he was able to make some progress: he found a generating function.
Next question: what is a generating function? To answer with an example, the generating function for the sequence is the power series .
More generally, the generating function for the sequence is a series: .
Next question: what’s the point? Often the resulting series can be radically compressed. For instance, a bit of mathematical magic tells us that the series can be rewritten[1] as . Now the whole infinite sequence has been encapsulated by a short, simple algebraic expression. So, if you want to know the th element of the sequence, you can extract it (if you know how) fairly easily from the generating function.
Well, there is not a lot of mystery in the sequence – certainly there are no prizes for guessing its th term. But what of the partition sequence: ? Euler’s great insight was that there is a generating function for this too:
You can see that this is not as nice as the function above – and it’s certainly not nice enough to close the book on the whole problem of computing partition numbers. All the same, this function is hugely easier to work with than scrabbling about with partitions with bare hands. Euler’s generating function can also be written as
On first sight, this looks like an algebraic nightmare: you have to open up an infinite number of brackets, each of which contains an infinite series! However, if you want to compute the th partition number, you only care about the first brackets, and only the first few terms in each: from the first bracket you care about the first terms, from the second bracket approximately the first , from the third approximately the first , and so on. In fact the total number of terms you need to worry about is approximately , which is a manageable number when is not too big.
So although Euler didn’t find a formula for partition numbers, his generating function does provide a manageable procedure for computing these numbers. But what of an actual formula?
Further progress came courtesy of a pair of mathematical superstars to rival Euler: Hardy and Ramanujan. The th one is given approximately by the formula
As grows bigger and bigger, this number gets proportionally closer to the right answer. But what about an exact formula? That’s something there has been huge progress on in recent years… but perhaps that’s a story for another day.
[1] There are issues of convergence here, which I will ignore for now.