The Pentagonal Number Theorem

Pick a number n and the page lists every way to write it as a sum of different positive whole numbers, as dot diagrams, paired off by Franklin’s move: one with an even number of parts beside one with an odd number. At most one is left without a partner, and only when n is a pentagonal number. Below, the product (1 − x)(1 − x²)… is multiplied out bracket by bracket, and its coefficients tell the same story.

Worked example — The Pentagonal Number Theorem

Even number of parts	7
Odd number of parts	8
Even minus odd	−1
p(12), by Euler’s recurrence	77
p(100)	190,569,292

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — The Pentagonal Number Theorem

Euler’s pentagonal number theorem: (1 − x)(1 − x²)(1 − x³)… = 1 − x − x² + x⁵ + x⁷ − x¹² − x¹⁵ + …, a sum over every whole number k, positive, negative or zero, of (−1)ᵏ x^(k(3k − 1)/2). The exponents are the generalised pentagonal numbers, and every coefficient is 0, +1 or −1.

What each symbol means

p(n): the number of partitions of n: ways to write it as a sum of positive whole numbers, order ignored
D₊(n), D₋(n): the partitions of n into different parts with an even, and with an odd, number of parts
k(3k ∓ 1)/2: the generalised pentagonal numbers 1, 2, 5, 7, 12, 15, 22, 26, …

Where the formula comes from

Why each coefficient is even minus odd. Multiplying out (1 − x)(1 − x²)(1 − x³)… means choosing, from every bracket, either 1 or −xᵏ. Choosing −xᵏ from some set of brackets gives x raised to the sum of those k, with one minus sign for each choice. So the coefficient of xⁿ gains +1 for every way to write n as a sum of different positive whole numbers with an even number of parts, and −1 for every way with an odd number. The theorem says that difference is zero except at the pentagonal numbers, where it is (−1)ᵏ.
Why Franklin’s move pairs them. In a diagram with different row lengths, let s be the smallest part and g the slope: how many rows, counting from the top, each step down by exactly one. If s ≤ g, take the bottom row and add one dot to the end of each of the top s rows; if s > g, take one dot from the end of each of the top g rows and make them a new bottom row of g. Either way the rows stay different, the total stays n, and the number of rows changes by one, so even and odd swap, and doing the move again undoes it. It is blocked only when the bottom row and the slope share a dot and s = g or s = g + 1. Those diagrams are k + (k + 1) + … + (2k − 1) and (k + 1) + … + 2k, whose totals are k(3k − 1)/2 and k(3k + 1)/2.
From the theorem to p(n). Every partition of n, repeats allowed, is counted by Σ p(n) xⁿ = 1/((1 − x)(1 − x²)(1 − x³)…). Multiply both sides by the product, which is the pentagonal series: (1 − x − x² + x⁵ + x⁷ − x¹² − …) × Σ p(n) xⁿ = 1. For n ≥ 1 the coefficient of xⁿ on the right is 0, so p(n) − p(n − 1) − p(n − 2) + p(n − 5) + p(n − 7) − … = 0. That is Euler’s recurrence, and the number of its terms grows only like √n.

Two hundred brackets, and only 23 of the first 201 coefficients survive 🖖

Multiply out (1 − x)(1 − x²) and you get 1 − x − x² + x³. Keep going one bracket at a time with the slider under the bar chart: the coefficients grow, reaching 31 partway through, and then cancel. After 200 brackets, only 23 of the first 201 coefficients are not zero, every one of them +1 or −1, and they sit at 0, 1, 2, 5, 7, 12, 15, 22, 26, … These are the pentagonal numbers, k(3k − 1)/2 and k(3k + 1)/2, and Euler found the pattern by multiplying the product out.

A pairing proves it: at 12 exactly one partition is left over 🖖

Press n = 9. The 8 ways to write 9 as a sum of different positive whole numbers split 4 with an even number of parts and 4 with an odd number, and Franklin’s move pairs every even one with an odd one. Press n = 12: 7 even against 8 odd, and one partition has no partner, 5 + 4 + 3, whose total, 12, is a pentagonal number. Click it and the page shows why the move is blocked there. The coefficient of x¹² is even minus odd, −1, and the pairing is the whole proof. Franklin, a student of Sylvester’s at Johns Hopkins, published it in 1881.

p(1000) takes 50 lookups 🖖

Turn the theorem round and it counts partitions p(n), sums in any order with repeats allowed. Euler’s recurrence uses only earlier values at pentagonal distances: p(12) = p(11) + p(10) − p(7) − p(5) + p(0) = 77. For p(1000), a number 32 digits long, that is 50 terms, and the whole table from p(1) to p(1000) takes 33,475 lookups against 500,500 additions done the plain way. Press p(200) for 3,972,999,029,388, the last entry in MacMahon’s table for Hardy and Ramanujan. Their famous formula’s first term is still 1.42% high at n = 1,000.

Problem solved in full

Euler’s “extraordinary law”: divisor sums from the same signs 4 steps
The signs that build p(n) also build the sum of the divisors of n. Euler called it a most extraordinary law. Use it to find σ(12), the sum of the divisors of 12, with one change to the recurrence: where it would need σ(0), use n itself.

Open this problem in the tool
1. The page’s recurrence for p(12), the pattern to copy:
  
  $p (12) = p (11) + p (10) - p (7) - p (5) + p (0) = 56 + 42 - 15 - 7 + 1 = 77$
2. The same offsets and signs for σ(12). The last offset is 12 itself, so σ(0) becomes 12:
  
  $σ (12) = σ (11) + σ (10) - σ (7) - σ (5) + σ (0) \to 12$
3. With σ(11) = 12, σ(10) = 18, σ(7) = 8 and σ(5) = 6:
  
  $σ (12) = 12 + 18 - 8 - 6 + 12 = 28$
4. Check by adding the divisors directly:
  
  $1 + 2 + 3 + 4 + 6 + 12 = 28$
Answer

σ(12) = 28. Euler wrote this up in 1747, and it holds for every n; the page’s own arithmetic checks it as far as n = 500.

$σ (12) = 28; σ (n) = \sum_{k} (- 1)^{k + 1} σ (n - \frac{k ( 3 k \mp 1 )}{2}), σ (0) \to n$

Learning path

Methods of proof

References (3)

Franklin's involution as stated on this page (compare the smallest part with the slope; move one onto the other; blocked only at the pentagonal diagrams), with Franklin's 1881 paper and his place as Sylvester's student at Johns Hopkins: I. Pak, "Partition bijections, a survey", The Ramanujan Journal 12, 5–75 (2006); preprint, §5.2.
Euler's paper on the sum of divisors, where the pentagonal signs that give p(n) give σ(n) too, the worked problem: L. Euler, "Découverte d'une loi tout extraordinaire des nombres par rapport à la somme de leurs diviseurs", Bibliothèque impartiale 3, 10–31 (written 1747, published 1751); Eneström number E175, The Euler Archive.
The partition numbers, Euler's recurrence over the generalised pentagonal numbers, Hardy and Ramanujan's asymptotic formula, and MacMahon's table of p(n) up to 200: OEIS Foundation, "A000041: a(n) = number of partitions of n" and "A001318: Generalized pentagonal numbers", The On-Line Encyclopedia of Integer Sequences.

By the 42Math team · Reviewed against published sources. Corrections welcome.