Integer Partitions

Counting p(n), and Euler's distinct-parts = odd-parts identity.

The idea

Definition (Partition).

A partition of a positive integer $n$ writes $n$ as a sum of positive integers, called its parts, with the order of the parts disregarded. The number of partitions of $n$ is written $p(n)$.

Splitting $n$ identical coins into piles illustrates why order is disregarded: a pile of $3$ with a pile of $1$ is the same split as a pile of $1$ with a pile of $3$, since nothing distinguishes the piles except their sizes. To list the partitions of $n$ without missing or repeating any, write each one's parts in non-increasing order and work through them systematically, largest first part first.

$p(n)$ has no simple closed form — nothing like $n!$ or $2^{n}$ or a ratio of factorials — and it grows quickly: $p(10) = 42$, while $p(100)$ exceeds $190$ million. The central theorems about partitions are instead identities: statements that the partitions of one restricted kind are exactly as numerous as those of another, for every $n$ at once. The first and most famous is Euler's.

Theorem (Euler's partition theorem).

For every positive integer $n$, the number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts.

Such an identity is proved by matching the two families up, never by computing either count.

Ways to work on it

• Walkthrough. List the partitions of small numbers, then restrict to distinct parts.
• Practice. Count the partitions of a small number.
• Hardest. Verify that partitions into distinct parts match partitions into odd parts.

Not sure where to start? Take the ten-question placement test.