Enumerative Combinatorics

In 1740 Philippe Naudé wrote to Leonhard Euler asking how many ways a number can be written as a sum of distinct parts. Euler's reply introduced a method that runs through combinatorics to this day. Multiply out

$$(1 + x)(1 + x^2)(1 + x^3)(1 + x^4) \cdots$$

and the coefficient of $x^n$ is the answer, because each way of picking terms from the brackets is a way of choosing distinct parts that add up to $n$. A whole sequence of answers is packed into one function. Algebra on the function, simplifying, multiplying, rearranging, then proves facts about the counts. Euler's Introductio of 1748 used it to prove results about partitions that nobody had noticed, let alone proved.

Partitions grow unpredictably fast. The number 10 has 42 of them, 100 has 190,569,292, and 200 has almost four trillion. In 1918 G. H. Hardy and Srinivasa Ramanujan, the self-taught Indian mathematician Hardy had brought to Cambridge, attacked Euler's generating function with the tools of complex analysis. They studied how it behaves near the edge of its circle of convergence and extracted a formula whose leading term is

$$p(n) \approx \frac{1}{4n\sqrt3}\, e^{\pi \sqrt{2n/3}} .$$

Percy MacMahon, a former artillery officer and a formidable calculator, had computed $p(200) = 3{,}972{,}999{,}029{,}388$ by hand. The full formula of Hardy and Ramanujan, with a few correction terms, matched it exactly. Two decades later Hans Rademacher turned it into an exact infinite series. A question about whole numbers had been answered with circles in the complex plane.

Write 7 as a sum of distinct positive whole numbers, ignoring order:

$$7, \quad 6+1, \quad 5+2, \quad 4+3, \quad 4+2+1 .$$

There are five. Now write 7 as a sum of odd numbers, repeats allowed:

$$7, \quad 5+1+1, \quad 3+3+1, \quad 3+1+1+1+1, \quad 1+1+1+1+1+1+1 .$$

Again five. This is no coincidence. Euler proved that for every number the two counts agree, and his generating functions show why in one line. Partitions into distinct parts are counted by $(1+x)(1+x^2)(1+x^3)\cdots$. Each factor can be rewritten as $1 + x^k = \dfrac{1 - x^{2k}}{1 - x^k}$, so the product is

$$\frac{1-x^2}{1-x} \cdot \frac{1-x^4}{1-x^2} \cdot \frac{1-x^6}{1-x^3} \cdot \frac{1-x^8}{1-x^4} \cdots$$

Every numerator $1 - x^{2k}$ cancels against a denominator further along. What survives are the denominators with odd exponents:

$$\frac{1}{(1-x)(1-x^3)(1-x^5)\cdots} .$$

That is the generating function for partitions into odd parts, since $\frac{1}{1-x^k} = 1 + x^k + x^{2k} + \cdots$ allows any number of copies of the part $k$. Two different counting problems have the same function, so they have the same answers.

Combinatorialists later found a proof that pairs the partitions off directly. If an odd part $k$ appears $m$ times, write $m$ as a sum of distinct powers of two and replace the copies with parts $k$ times each power. Three copies of 1 become $2 + 1$, and two copies of 3 become 6. Every partition into odd parts turns into exactly one partition into distinct parts, and back. That kind of explicit matching, a bijection, has become the standard the field aims for.

Many counting problems care about shape, not labels. How many different necklaces can be made from four black and four white beads, when turning a necklace round does not make it different? How many molecules have the formula $\text{C}_{6}\text{H}_{14}$? In 1937 George Pólya showed how to average over the group of symmetries to get the answer, as J. Howard Redfield had in a 1927 paper that almost nobody read. Group theory became a counting tool.

By the 1960s the subject was a large collection of techniques with little theory connecting them. Gian-Carlo Rota began to supply one in 1964, and counting became a branch of mathematics with its own journals, conjectures and open problems. Some of those problems are about existence rather than number. Whether a Hadamard matrix exists for every multiple of four, a question from 1933, is still open. Order 668 was the smallest missing case until 2026.