# Pentagonal number theorem

In mathematics, the pentagonal number theorem, originally due to Euler, relates the product and series representations of the Euler function. Pentagonal number theorem_sentence_0

It states that Pentagonal number theorem_sentence_1

In other words, Pentagonal number theorem_sentence_2

A striking feature of this formula is the amount of cancellation in the expansion of the product. Pentagonal number theorem_sentence_3

## Relation with partitions Pentagonal number theorem_section_0

or more formally, Pentagonal number theorem_sentence_4

## Bijective proof Pentagonal number theorem_section_1

The theorem can be interpreted combinatorially in terms of partitions. Pentagonal number theorem_sentence_5

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. Pentagonal number theorem_sentence_6

Each partition of n into an even number of distinct parts contributes +1 to the coefficient of x; each partition into an odd number of distinct parts contributes −1. Pentagonal number theorem_sentence_7

(The article on unrestricted partition functions discusses this type of generating function.) Pentagonal number theorem_sentence_8

For example, the coefficient of x 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 (the one-part partition 5). Pentagonal number theorem_sentence_9

However, the coefficient of x 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. Pentagonal number theorem_sentence_10

This interpretation leads to a proof of the identity via involution (i.e. a bijection which is its own inverse). Pentagonal number theorem_sentence_11

Consider the Ferrers diagram of any partition of n into distinct parts. Pentagonal number theorem_sentence_12

For example, the diagram below shows n = 20 and the partition 20 = 7 + 6 + 4 + 3. Pentagonal number theorem_sentence_13

Pentagonal number theorem_description_list_0

Let m be the number of elements in the smallest row of the diagram (m = 3 in the above example). Pentagonal number theorem_sentence_14

Let s be the number of elements in the rightmost 45 degree line of the diagram (s = 2 dots in red above, since 7−1 = 6, but 6−1 > 4). Pentagonal number theorem_sentence_15

If m > s, take the rightmost 45-degree line and move it to form a new row, as in the diagram below. Pentagonal number theorem_sentence_16

Pentagonal number theorem_description_list_1

If m ≤ s (as in our newly formed diagram 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 diagram. Pentagonal number theorem_sentence_17

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 diagram. Pentagonal number theorem_sentence_18

This enables us to pair off Ferrers diagrams contributing 1 and −1 to the x term of the series, resulting in a net coefficient of 0. Pentagonal number theorem_sentence_19

This holds for every term except when the process cannot be performed on every Ferrers diagram with n dots. Pentagonal number theorem_sentence_20

There are two such cases: Pentagonal number theorem_sentence_21

1) m = s and the rightmost diagonal and bottom row meet. Pentagonal number theorem_sentence_22

For example, Pentagonal number theorem_sentence_23

Pentagonal number theorem_description_list_2

Attempting to perform the operation would lead us to: Pentagonal number theorem_sentence_24

Pentagonal number theorem_description_list_3

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 diagram. Pentagonal number theorem_sentence_25

If there are m elements in the last row of the original diagram, then Pentagonal number theorem_sentence_26

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

2) m = s+1 and the rightmost diagonal and bottom row meet. Pentagonal number theorem_sentence_28

For example, Pentagonal number theorem_sentence_29

Pentagonal number theorem_description_list_4

Our operation requires us to move the right diagonal to the bottom row, but that would lead to two rows of three elements, forbidden since we're counting partitions into distinct parts. Pentagonal number theorem_sentence_30

This is the previous case but with one fewer row, so Pentagonal number theorem_sentence_31

where we take k = 1−m (a negative integer). Pentagonal number theorem_sentence_32

Here the associated sign is (−1) with s = m−1 = −k, therefore the sign is again (−1). Pentagonal number theorem_sentence_33

## Partition recurrence Pentagonal number theorem_section_2

Note that is the reciprocal of the product on the left hand side of our identity: Pentagonal number theorem_sentence_34

In terms of sets of partitions, this is equivalent to saying that the following sets are of equal cardinality: Pentagonal number theorem_sentence_35

This is an involution (a self-inverse mapping), and thus in particular a bijection, which proves our claim and the identity. Pentagonal number theorem_sentence_36