Pentagonal number theorem

In mathematics, the pentagonal number theorem, originally due to Euler, states that

This theorem can be given a combinatorial interpretation in terms of partitions. In particular, the left hand side is a generating function (for similar reasons as the generating function for the more generalized unrestricted partition function) for the number of partitions of n into an even number of distinct parts minus the number of partitions of n into an odd number of distinct parts.

For example, the x⁵ coefficient, is 1 because of there are two ways to split 5 into an even number of distinct parts (4+1 and 3+2), but only one way to do so for an odd number of distinct parts (5 itself).

This interpretation leads to an elegant proof of the identity via involution. Consider the Ferrers graph of any partition of n into distinct parts. (in the diagram below n=20 and the partition is 7+6+4+3)

o o o o o o +
o o o o o +
o o o o
o o o

Let k be the number of elements in the smallest row of our graph. Let s be the number of elements in the rightmost 45 degree line of our graph (marked by a plus sign in the above diagram). In the diagram above, s=2 and k=3

If k>s, we take the rightmost 45 degree line and move it to form a new row, as in the graph below.

o o o o o o
o o o o o
o o o o
o o o
+ +

If this is not the case (as in our newly formed graph where k=2, s=5) we reverse the process by moving the bottom row to form a new 45 degree line (in effect adding 1 element to each of the first k rows). In our case, this takes us back into the first graph.

A bit of thought shows that in fact applying this process twice brings us back to the original graph and the process always changes the parity of the number of rows. Thus this process (when it can be performed) enables us to pair off the Ferrers' graphs of partitions contributing 1 and -1 to the original sum. Everything cancels, UNLESS there are some cases where our operation cannot be performed. In fact, there are two of them.

1) k=s and the rightmost diagonal and bottom row meet. For example,

o o o o o
o o o o
o o o

Attempting to perform the operation would lead us to:

o o o o o o
o o o o o
      o  

which is not a valid Ferrers' graph. If there are k elements in the last row of the original graph, then

2) k=s-1 and the rightmost diagonal and bottom row meet. For example,

o o o o o o
o o o o o
o o o o

Our operation requires us to move the right diagonal to the bottom row, but that would lead to two rows of 3 elements, forbidden since we're counting partitions into distinct parts. This is the previous case but with an extra element in each row, so

In summary, we have shown that partitions into an even number of distinct parts and an odd number of distinct parts exactly cancel each other out, except for pentagonal numbers, where there is exactly one case left over (which contributes a factor of (-1)^k). But this is precisely what the right side of the identity says should happen, so we are finished.