Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 36 ยท Partitions and Catalan Numbers

Ferrers Diagrams and Pentagonal Numbers

Draw partitions as Ferrers diagrams, flip them to get conjugates, prove partition identities by bijection, and compute p(n) fast with Euler's pentagonal number theorem.

A Ferrers diagram draws a partition as rows of dots, largest row on top. The partition 5 + 3 + 3 + 1 is a left-justified picture with rows of length 5, 3, 3 and 1. Pictures turn many partition facts into one-line proofs: you flip, rotate or slice the diagram and see an identity.

Conjugate partitions

Reflect a Ferrers diagram across its diagonal (rows become columns). The result is the conjugate partition. Reading the column heights of 5 3 3 1 gives 4 3 3 1 1. Conjugating twice returns the original, so conjugation is a bijection between partitions of n with itself.

What does it do to the statistics?

  • The number of parts of p becomes the largest part of the conjugate.
  • Therefore partitions of n with at most k parts correspond one-to-one with partitions of n with largest part at most k. That is the pattern we saw in the previous lesson.

Self-conjugate partitions

A partition is self-conjugate when its diagram is symmetric about the diagonal. Peel off the outer "hook" (first row plus first column): its length is odd. Peel the next hook, and so on. Hook lengths are distinct odd numbers that strictly decrease. Conversely, any set of distinct odd numbers builds a symmetric diagram. Hence:

The number of self-conjugate partitions of n equals the number of partitions of n into distinct odd parts.

Python Draw, conjugate and count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two columns agree for every n from 1 to 14, exactly as the hook argument predicts.

flowchart LR
    A["Partition p"] -->|"transpose rows and columns"| B["Conjugate p'"]
    B -->|"transpose again"| A
    A -.-> C["parts(p) = largest(p')"]

Conjugation swaps number of parts with size of the largest part.

Euler's pentagonal number theorem

Start from the generating function of p(n), P(x) = 1/prod(1 - x^k). Its reciprocal, the infinite product prod(1 - x^k), expands to a series with an astonishingly sparse form:

prod (1 - x^k) = 1 - x - x^2 + x^5 + x^7 - x^12 - x^15 + x^22 + x^26 - ...

The exponents are the generalized pentagonal numbers k(3k - 1)/2 for k = 1, -1, 2, -2, 3, ..., namely 1, 2, 5, 7, 12, 15, 22, 26, ... and the signs go - - + + - - + +. Multiplying P(x) by this series gives 1, so for n >= 1:

p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - ...

Only about sqrt(n) terms appear, so computing all p(0..n) takes O(n sqrt n) time, much faster than the O(n^2) DP.

Python Pentagonal recurrence for p(n)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

p(200) = 3,972,999,029,388, and every value matches sympy. The last line lists the first pentagonal numbers 1, 5, 12, 22, 35, 51; their partners k(3k+1)/2 give 2, 7, 15, 26, ...

A combinatorial view of the theorem

Franklin's proof pairs partitions of n into an even number of distinct parts with those into an odd number, by moving the smallest part onto the first few rows or back. The pairing works perfectly except when the Ferrers diagram forms a "pentagonal" shape, leaving exactly one unpaired partition. That is why the series has coefficients only 0, +1, -1 and appears at pentagonal exponents.

Hardy and Ramanujan (and later Rademacher) found an exact formula for p(n) as a convergent series, and the growth rate exp(pi sqrt(2n/3)) / (4 n sqrt3). For everyday work the pentagonal recurrence is the practical algorithm.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the conjugate of the partition 4 + 2 + 1?

    Column heights of rows 4,2,1 are 3, 2, 1, 1, so the conjugate is 3 + 2 + 1 + 1.
  2. 2. Conjugation turns the number of parts into which statistic?

    Rows of the original become columns, so the row count becomes the length of the first row.
  3. 3. Self-conjugate partitions of n are in bijection with partitions of n into...

    Each diagonal hook has odd length, and the hooks have strictly decreasing sizes.
  4. 4. Which numbers appear as exponents in Euler's pentagonal theorem?

    The exponents are 1, 2, 5, 7, 12, 15, ..., the generalized pentagonal numbers.

Summary

  • A Ferrers diagram draws a partition; transposing gives the conjugate partition.
  • Parts and largest part swap under conjugation; self-conjugate means symmetric and equals distinct odd parts.
  • Euler's pentagonal theorem gives p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + ..., an O(n sqrt n) algorithm.

Next: Catalan Numbers