Pentagonal Number Theorem - Bijective Proof

Bijective Proof

The theorem can be given a combinatorial interpretation in terms of partitions. In particular, the left hand side is a generating 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. Each partition of n into an even number of distinct parts contributes +1 to the coefficient of xn; each partition into an odd number of distinct parts contributes −1. (The article on unrestricted partition functions discusses this type of generating function.)

For example, the coefficient of x5 is +1 because 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). However, the coefficient of x12 is −1 because there are seven ways to partition 12 into an even number of distinct parts, but there are eight ways to partition 12 into an odd number of distinct parts.

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

Let m be the number of elements in the smallest row of our graph (m = 3 in the above example). Let s be the number of elements in the rightmost 45 degree line of our graph (s = 2 dots in red above, since 7−1 = 6, but 6−1 > 4). If m > s, we take the rightmost 45 degree line and move it to form a new row, as in the graph below.

If m ≤ s (as in our newly formed graph where m = 2, s = 5) we may reverse the process by moving the bottom row to form a new 45 degree line (adding 1 element to each of the first m rows), taking us back to the first graph.

A bit of thought shows that this process always changes the parity of the number of rows, and applying the process twice brings us back to the original graph. This enables us to pair off the Ferrers' graphs contributing 1 and −1 to the xn term of the series, resulting in a net coefficient of 0. This holds for every term except when the process cannot be performed on every Ferrers graph with n dots. There are two such cases:

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

Attempting to perform the operation would lead us to:

which fails to change the parity of the number of rows, and is not reversible in the sense that performing the operation again does not take us back to the original graph. If there are m elements in the last row of the original graph, then

where the new index k is taken to equal m. Note that the sign associated with this partion is (−1)s, which by construction equals (−1)m and (−1)k.

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

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 one fewer row, so

where we take k = 1−m (a negative integer). Here the associated sign is (−1)s with s = m−1 = −k, therefore the sign is again (−1)k.

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, except if n is a generalized pentagonal number, in which case there is exactly one Ferrers graph left over. But this is precisely what the right side of the identity says should happen, so we are finished.