In 1740, French mathematician Philippe Naudé wrote to Leonhard Euler asking in how many ways a positive integer can be written as a sum of distinct numbers. In his investigations of this, Euler established the theory of partitions, for which he used the term *partitio numerorum.*

Many of Euler’s results in number theory involved divergent series. He was courageous in manipulating these but had remarkable insight and, almost invariably, his findings, although not rigorously established, were valid.

** Partitions**

In number theory, a *partition* of a positive integer is a way of writing as a sum of positive integers. The order of the summands is ignored: two sums that differ only in their order are considered the same partition.

The *partition function*, , is the number of possible partitions of . For example, since the integer has five partitions:

The values of for from to are

A wonderful asymptotic formula for was obtained by G. H. Hardy and Srinivasa Ramanujan in 1918:

Twenty years later, a complete asymptotic expansion was presented by Hans Rademacher.

**Euler’s Brilliant Reasoning**

Restricted partitions satisfy some additional condition. Notable among these are *distinct partitions*, where each summand is different, and *odd partitions*, where each summand is odd. For each positive number, the number of partitions with odd parts is equal to the number of partitions with distinct parts, denoted by . This result was proved by Leonhard Euler in 1748.

A simple trial gives the number of distinct partitions for the first 10 numbers. For example the number 6 can be expressed as

A recurrence relation would seem to be involved but, based on an examination of the sequence , no such relationship appears obvious.

Euler also examined another partition, into odd numbers but allowing repetitions. Thus, for the number 6 we get

so, again there are four possibilities. This is no coincidence, as Euler was quick to show.

Let us denote by the number of *distinct* partitions of and by the number of partitions in *odd* numbers. Euler proved that, for all these two quantities are equal.

Euler quickly realized that, for the question raised by Philippe Naud\'{e}, a generating function could be written down easily — that is, *easily for Euler*, but amazing for mere mortals — that leads to the answer. He went far beyond answering Naudé‘s question and his proof was a truly bravura performance.

** Distinct Partitions **

Euler saw that, if he defined an infinite power series

he could construct it from simple factors. He wrote down the infinite product

and formally multiplied all the factors to deduce the coefficient of each power of .

Take for example the sixth power of . This can be obtained as follows

- Take the term from the factor and from all other factors.
- Take the term from , from and from all other factors.
- Take the term from , from and from all other factors.
- Take the term from , from , from and otherwise.

These four choices correspond to the partitioning of 6 into distinct whole numbers, so the coefficient of is . Clearly, this argument is general: the coefficient of is and the infinite product (2) is equivalent to the infinite polynomial (1). Distinctiveness of the partition is guaranteed since each power of is found in only one factor.

**Partitions in Odd Terms**

Euler now introduced the infinite product

with odd powers of in the denominator. Using the binomial theorem, we have

* (1-x )^{-1} = 1 + (x)^1 + (x^2)^1 + (x^3)^1 + … (4)*

*(1-x^3)^{-1} = 1 + (x^3) + (x^3)^2 + (x^3)^3 + … (5)*

*(1-x^5)^{-1} = 1 + (x^5) + (x^5)^2 + (x^5)^3 + … (6)*

We can multiply all the right hand sides to get . Let us examine the coefficient of .

- Pick from (4) and 1 elsewhere.
- Pick from (6), from (1) and 1 elsewhere.
- Pick from (4), from (5) and 1 elsewhere.
- Pick from (5) and 1 elsewhere.

These choices correspond to the four ways of partitioning 6 into odd numbers. Formally, we can write the product as

Now comes Euler’s *coup de grace*: by multiplying above and below by the “missing even terms”, he got

Then, factoring each term in the numerator and cancelling, he obtained

But this is identical to the axpression (2) for . Thus, Euler showed that the polynomials and are the same. So, their coefficients of each power of must be the same:

or, in words, **the number of partitions with odd parts is equal to the number of partitions with distinct parts.**

**Conclusion**

Euler was able to give an immediate answer to Naudé ‘s question on the partition of numbers because he had already been studying the properties of power series. In studying the relationship between a series and a product, Euler made a momentous discovery, an identity relating a sum over all the numbers to a product over all the primes :

In 1745 his old teacher Johann Bernoulli addressed him as *Mathematicorum Princeps* — the Prince of Mathematicians. Lagrange and Gauss were later to be honoured with this title, but Euler was the first (Shiu, 2007).

** Acknowledgement **

William Dunham (1994) describes Euler’s ingenuity as “simply astonishing”. This article owes much to the chapter on Euler in Dunham’s book.

** Sources **

Shiu, Peter, 2007: Euler’s Contribution to Number Theory. *The Math. Gazette*, **91**, No. 522, 453-461.

Dunham, William, 1994: *The Mathematical Universe.* John Wiley & Sons. 314pp. ISBN: 978-0-4711-7661-9.