Playing with Partitions: Euler’s Pentagonal Theorem

Introduction

Today we will play a small game which is really really simple. We will add up numbers to make numbers. And to keep the matters simple we will only deal with counting numbers \(1, 2, 3, \ldots\) As an example \(2 + 3 = 5\), but to make the game challenging we would reverse the problem. Let’s ask how we can split \(5\) into sum of other numbers. For completeness we take \(5\) also as one of the ways to express \(5\) as sum of numbers. Clearly we have the following other ways $$ 5 = 4 + 1 = 3 + 1 + 1 = 3 + 2 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1$$ so that there are \(7\) different ways of adding numbers to make \(5\). We don’t take into account the order of summands. Also one number can be repeated if needed.

Partitions of a Number

It turns out that a whole generation of distinguished mathematicians (Euler, Jacobi, Ramanujan, Hardy, Rademacher etc) were also interested in playing the above game. And needless to say, they made the whole thing very systematic by adding some definitions (its their silly habit so to speak). Following their footprints we say that a tuple \((n_{1}, n_{2}, \ldots, n_{k})\) of positive integers is a partition of a positive integer \(n\) if $$n_{1} \geq n_{2} \geq \cdots \geq n_{k}\text{ and }n_{1} + n_{2} + \cdots + n_{k} = n$$ Thus \((3, 2), (3, 1, 1)\) etc are partitions of \(5\). If \((n_{1}, n_{2}, \ldots, n_{k})\) is a partition of \(n\) then we say that each of the \(n_{i}\) is a part of this partition, \(k\) is the number of parts, \(n_{1}\) is the greatest part and \(n_{k}\) the least part of this partition.

The mathematicians were really not so interested in finding individual partitions of a number \(n\), but were rather interested in finding out the total number of partitions of \(n\). The example above deals with \(n = 5\) and clearly there are \(7\) partitions of \(5\). You should convince yourself by taking a slightly larger number, say \(n = 8\) or \(n = 10\), that finding the number of partitions of any given number \(n\) is not that easy. Especially writing out each partition of \(n\) and then counting them all is very difficult. You may always feel that probably you have missed one of the partitions. Mathematicians however found out a smart way to count partitions. We explore this technique further.

Counting via Method of Coefficients

To count partitions of \(n\) we need to count tuples \((n_{1}, n_{2}, \ldots, n_{k})\) such that \(n_{1} + n_{2} + \cdots + n_{k} = n\). Let us first try to solve a simpler problem. Suppose we need to find tuples \((x, y)\) such that \(x + y = 10\). Also let’s assume that \(x, y\) may be zero or positive integers. Clearly we have only \(11\) options \((0, 10), (1, 9), \ldots, (10, 0)\). Here we are paying attention to order also.

Let’s try to count tuples \((x, y, z)\) satisfying \(x + y + z = 10\). That does not seem so easy like the previous problem. But let’s work methodically. Let \(x = 0\) so that \(y + z = 10\) and we have \(11\) tuples \((y, z)\) for this problem. If \(x = 1\) then \(y + z = 9\) and we have \(10\) tuples \((y, z)\) satisfying \(y + z = 9\). Similarly we try for \(x = 2, 3, \ldots, 10\) and then the total count of all the tuples \((x, y, z)\) is $$11 + 10 + 9 + \cdots + 1 = \frac{11\cdot 12}{2} = 66$$ Following this argument we can see that the number of non-negative integral solutions to \(x + y + z = n\) is \((n + 1)(n + 2)/2\). Similarly this argument can be extended to show that the number of solutions to $$x_{1} + x_{2} + \cdots + x_{m} = n$$ is \(\displaystyle \binom{n + m – 1}{m – 1}\).

There is however another simple way to get the same result. Consider the expression $$(1 + x + x^{2} + \cdots + x^{i} + \cdots)(1 + x + x^{2} + \cdots + x^{j} + \cdots) = \frac{1}{1 – x}\cdot\frac{1}{1 – x}$$ If we multiply the two series on left side we get expressions of type \(x^{i + j}\) and there will be as many terms like \(x^{n}\) as there are number of solutions to \(i + j = n\). It follows (also note the right side) that the number of non-negative integer solutions to \(i + j = n\) is equal to the coefficient of \(x^{n}\) in \((1 – x)^{-2}\). Similarly the number of solutions to \(x_{1} + x_{2} + \cdots + x_{m} = n\) is the coefficient of \(x^{n}\) in \((1 – x)^{-m}\).

As a variation if we want solutions \((i, j)\) with \(i \geq 1, j \geq 2\) and \(i + j = n\) then we need to start the series corresponding to \(i\) with \(x\) and that for \(j\) with \(x^{2}\) so that the number of solutions is equal to the coefficient of \(x^{n}\) in $$(x + x^{2} + \cdots)(x^{2} + x^{3} + \cdots) = x^{3}(1 – x)^{-2}$$ Let’s now try out the equation \(i + 2j = n\). In this case the series should look like $$(1 + x + x^{2} + \cdots + x^{i} + \cdots)(1 + x^{2} + x^{4} + \cdots + x^{2j} + \cdots) = \frac{1}{(1 – x)(1 – x^{2})}$$ Similarly we can handle equations like \(i + 2j + 3k + l = n\).

Now we get back to counting partitions of \(n\). Clearly the least part in a partition can be \(1\) and the largest part can be \(n\). Let the integer \(i\) be a part in a partition of \(n\) and let it be repeated \(k_{i}\) times in that partition so that $$1\cdot k_{1} + 2 \cdot k_{2} + \cdots + n\cdot k_{n} = n$$ Now each of the variables \(k_{1}, k_{2}, \ldots, k_{n}\) is a non-negative integer. Thus total number of partitions of \(n\) is equal to the number of solutions of the above equation. However there is a catch here as the number of variables \(k_{1}, k_{2}, \ldots\) is itself dependent on \(n\). It turns out that the corresponding product is of the form $$(1 + x + \cdots + x^{1\cdot k_{1}} + \cdots)(1 + x^{2} + \cdots + x^{2\cdot k_{2}} + \cdots)\cdots(1 + x^{i} + \cdots + x^{i \cdot k_{i}} + \cdots)\cdots$$ and this evaluates to $$\frac{1}{(1 – x)(1 – x^{2})(1 – x^{3})\cdots}$$ It follows that if \(p(n)\) is the number of partitions of \(n\) and \(p(0) = 1\) then $$\sum_{n = 0}^{\infty}p(n)x^{n} = \frac{1}{(1 – x)(1 – x^{2})(1 – x^{3})\cdots}$$ In case of simple equations like \(i + 2j = n\) the products used to get simplified in the form of a finite number of terms of type \(1/(1 – x^{i})\) and using binomial theorem and multiplication of series we could get a finite formula for the number of solutions to \(i + 2j = n\) in terms of \(n\). But for the expression $$\frac{1}{(1 – x)(1 – x^{2})(1 – x^{3})\cdots}$$ we don’t have a general formula for the \(n^{\text{th}}\) term (because of the infinite number of factors involved). Are we doomed then?

Euler’s Pentagonal Theorem

Luckily the answer is No and we have some saving grace as we do have a formula for the \(n^{\text{th}}\) term of $$(1 – x)(1 – x^{2})(1 – x^{3})\cdots$$ Euler found this formula by multiplying the product by hand to get terms upto \(x^{52}\) and guessed a pattern for the coefficients in the resulting series. However it took him some years to give a theoretical justification for the formula and thereby provide a sound proof. We have the formula $$(1 – x)(1 – x^{2})(1 – x^{3})\cdots = \sum_{j = -\infty}^{\infty}(-1)^{j}x^{(3j^{2} + j)/2}$$ so that we have to form terms for all integral values of \(j\) (negative and zero also included) and for each \(j\) we have a term \(x^{(3j^{2} + j)/2}\) and its coefficient is \((-1)^{j}\). Thus there is a term like \(x^{k}\) in the above series expansion if and only if \(k\) is of the form \((3j^{2} + j)/2\) with \(j\) being some integer. Such numbers \(k\) are called pentagonal numbers and for this very reason the Euler’s formula above is called the Pentagonal Theorem.

Putting \(j = 0, -1, 1, -2, 2, -3, 3\) we get the first few terms of the series as $$1 – x – x^{2} + x^{5} + x^{7} – x^{12} – x^{15} + \cdots$$ As we have mentioned earlier it took some years for Euler to prove his formula and one might expect the proof to be extremely difficult. It turns out that the proof is not difficult but definitely very non-obvious and requires good amount of heavy mathematical machinery. Near the end of nineteenth century an American mathematician F. Franklin found a marvelous proof which involved no machinery at all, but rather arguments of a very different nature (termed “combinatorial” nowadays). This is what we discuss next.

Combinatorial Proof of Euler’s Pentagonal Theorem

Rather than focusing on \((1 – x)(1 – x^{2})\cdots\) let us first focus on $$(1 + x)(1 + x^{2})(1 + x^{3})\cdots$$ which might be simpler because of two reasons:

• it involves only \(+\) signs
• it is already of the form \((1 + x^{i} + \cdots)(1 + x^{j} + \cdots)\cdots\)

This second part really helps us a lot and tells us that the coefficient of \(x^{n}\) in the new product can be interpreted as the number of solutions to \(k_{1} + k_{2} + \cdots + k_{j} = n\) where all the \(k\)’s are different (apart from \(x^{0} = 1\) none of the factors has same power of \(x\)). This means that the coefficient of \(x^{n}\) in $$(1 + x)(1 + x^{2})(1 + x^{3})\cdots$$ gives us the number of partitions of \(n\) with distinct parts.

Thus for \(n = 5\) we have three such partitions \((5), (4, 1), (3, 2)\). Let \(q(n)\) be the coefficient of \(x^{n}\) in \((1 + x)(1 + x^{2})\cdots\) then \(q(5) = 3\). Also we split \(q(n)\) into multiple terms based on number of parts so that \(q_{k}(n)\) denotes the number of partitions of \(n\) into \(k\) distinct parts and we have $$q(n) = q_{1}(n) + q_{2}(n) + \cdots = \sum_{k \geq 1}q_{k}(n)$$ We can now attack our original problem of finding coefficient \(r(n)\) of \(x^{n}\) in the product $$(1 – x)(1 – x^{2})(1 – x^{3})\cdots$$ Clearly when we multiply the individual factors and consolidate the terms \(x^{n}\) we get terms corresponding to each partition of \(n\) with distinct parts, but not each such term will be added (like in case of the product \((1 + x)(1 + x^{2})\cdots\)), rather each such term will have a \(+\) or a \(-\) sign depending on the number of parts in the partition (if number of parts is even then it will be \(+\) otherwise a \(-\)). Thus to get \(x^{5}\) we have three terms namely \(-x^{5}, x^{5}, x^{5}\) corresponding to the partitions \((5), (4, 1), (3, 2)\) respectively. So the net result is the term \(x^{5}\).

It follows that $$r(n) = -q_{1}(n) + q_{2}(n) – q_{3}(n) + \cdots = \sum_{k \geq 1}(-1)^{k}q_{k}(n)$$ where \(r(n)\) is the coefficient of \(x^{n}\) in $$(1 – x)(1 – x^{2})(1 – x^{3})\cdots$$ Thus to find the coefficient \(r(n)\) we need to count partitions of \(n\) with distinct parts and try to see “how many (say \(A\)) of them have even number of parts” and “how many (say \(B\)) have odd number of parts”. Then \(r(n) = A – B\). Franklin’s great (and at the same time simple) idea was to analyze the partitions of \(n\) with distinct parts and show that most of the time there would be a pairing between partitions with even number of parts and those with odd number of parts so that mostly \(A = B\) and hence the coefficient \(r(n) = 0\).

Only in the exceptional cases there will be a few partitions (of “even” or “odd” type) which will be left out without any pairing with opposite type. Franklin found out exactly which partitions could be paired up and which ones could not. He found that depending on value of \(n\) either there will be no exceptional partitions of this kind or there will be at most only one such partition. We present Franklin’s beautiful idea next.

Franklin’s Pairing of Partitions

To proceed further we fix a pictorial notation for a given partition. If \((n_{1}, n_{2}, \ldots, n_{k})\) is a partition then it is represented as a left-aligned two dimensional array of dots such such that number of rows in the array is equal to the number of parts in the partition (\(k\)) and the \(i^{\text{th}}\) row contains \(n_{i}\) dots. Thus the partition \((5, 4, 2, 2)\) is represented as Such a notation is very helpful in analyzing the nature of partitions and is the key to most of the combinatorial proofs in the theory of partitions.

Franklin was analyzing partitions with distinct parts via their graphical representations. He found that under certain conditions a partition with odd number of parts could be transformed into a partition with even number of terms and vice versa. His idea was to start with the first row of dots and continue till we get consecutively decreasing series of dots in each successive row. Thus for \((9, 8, 7, 5, 4)\) we can start with first row of \(9\) dots and then continue till third row of \(7\) dots. We have \(3\) such rows from top where the parts (or dots) decrease one by one. If the number of such rows is less than the last part (which is the case here as last part is \(4\)) then we can remove the last dots from each of these rows and put it after the last row to make another partition (which also has distinct parts and total number of dots remains same) which has an extra row. This changes the number of rows by one and thereby its parity. The procedure can be reversed if the number of parts is at least one more than the last part. We show this pairing below for the partitions \((9, 8, 7, 5, 4)\) and \((8, 7, 6, 5, 4, 3)\). More formally let \((n_{1}, n_{2}, \ldots, n_{k})\) be a partition of \(n\) with distinct parts and let \(j\) be the smallest integer for which \(n_{j + 1} < n_{j} – 1\). If \(j < n_{k}\) then the last dots of first \(j\) rows can be removed and put as \((k + 1)^{\text{th}}\) row to make a partition with \((k + 1)\) distinct parts. If \(j \geq n_{k}\) then the \(k^{\text{th}}\) row can be removed and its dots can be placed one by one at the end of each row starting from first row.

This rearrangement will fail if \(j = k = n_{k}\) or \(j = k = n_{k} – 1\) and will work in all the other cases. In the first case we have $$n = j + (j + 1) + \cdots + (2j – 1) = \frac{3j^{2} – j}{2}$$ and in the second case $$n = (j + 1) + (j + 2) + \cdots + 2j = \frac{3j^{2} + j}{2}$$ In these two cases we are left with an unpaired partition with \(j\) parts.

In now follows that the sum \(r(n) = \sum_{k \geq 1}(-1)^{k}q_{k}(n)\) is \(0\) if \(n\) is not of the form \(n = (3j^{2} \pm j)/2\) and is \((-1)^{j}\) otherwise. We thus have $$(1 – x)(1 – x^{2})(1 – x^{3})\cdots = 1 + \sum_{j = 1}^{\infty}(-1)^{j}x^{(3j^{2} + j)/2} + \sum_{j = 1}^{\infty}(-1)^{j}x^{(3j^{2} – j)/2}$$ which is also written as $$(1 – x)(1 – x^{2})(1 – x^{3})\cdots = \sum_{j = -\infty}^{\infty}(-1)^{j}x^{(3j^{2} + j)/2}$$ which is the Euler’s Pentagonal Theorem.

Counting Partitions via Euler’s Pentagonal Theorem

We now have the formula $$\sum_{n = 0}^{\infty}p(n)x^{n} = \frac{1}{(1 – x)(1 – x^{2})\cdots} = \dfrac{1}{{\displaystyle \sum_{n = -\infty}^{\infty}(-1)^{n}x^{(3n^{2} + n)/2}}}$$ or $$\left(1 + \sum_{n = 1}^{\infty}p(n)x^{n}\right)\left(1 + \sum_{n = 1}^{\infty}(-1)^{n}x^{(3n^{2} + n)/2} + \sum_{n = 1}^{\infty}(-1)^{n}x^{(3n^{2} – n)/2}\right) = 1$$ Equating coefficients of \(x^{n}\) on both sides gives us a recursive relation to calculate \(p(n)\) namely $$p(n) = p(n – 1) + p(n – 2) – p(n – 5) – p(n – 7) + p(n – 12) + p(n – 15) – \cdots$$ where the pattern \(1, 2, 5, 7, 12, 15,\ldots\) is the sequence of pentagonal numbers of the form \((3j^{2} \pm j)/2\). We start with \(p(1) = 1\) and the convention that \(p(0) = 1, p(n) = 0\) if \(n < 0\). We have the next few calculations $$\begin{aligned}p(2) &= p(1) + p(0) = 2\\ p(3) &= p(2) + p(1) = 3\\ p(4) &= p(3) + p(2) = 5\\ p(5) &= p(4) + p(2) – p(0) = 7\\ p(6) &= p(5) + p(4) – p(1) = 11\\ p(7) &= p(6) + p(5) – p(2) – p(0) = 15\\ p(8) &= p(7) + p(6) – p(3) – p(1) = 22\\ p(9) &= p(8) + p(7) – p(4) – p(2) = 30\\ p(10) &= p(9) + p(8) – p(5) – p(3) = 42\end{aligned}$$ Indian mathematician S. Ramanujan was not so happy calculating partitions in this manner (because it involved keeping a table of all previously calculated values) and he gave an almost exact formula for \(p(n)\) in terms of \(n\) which was further refined by Hans Rademacher into an exact formula. It is of interest to note that before the Ramanujan-Rademacher formula, Euler’s pentagonal theorem was the only way out to calculate partitions of a number. The approach by Ramanujan is considerably more difficult to understand but is a gem of mathematics and we will have occasion to discuss it later on this blog.