The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts

Solution 1:

I'll give a sketch of the bijective proof; ask me if there's some part you don't understand and need fleshed out (or maybe someone else will post a detailed version).

The important idea is that every number can be expressed uniquely as a power of 2 multiplied by an odd number. (Divide the number repeatedly by 2 till you get an odd number.) For instance, $120 = 2^3 \times 15$ and $68 = 2^2 \times 17$ and $81 = 2^0 \times 81$.

Odd parts -> Distinct parts

Suppose you are given a partition of n into odd parts. Count the number of times each odd number occurs: suppose $1$ occurs $a_1$ times, similarly $3$ occurs $a_3$ times, etc. So $n = a_11 + a_33 + a_55 + \cdots$.

Now write each $a_i$ "in binary", i.e., as a sum of distinct powers of two. So you have $n = (2^{b_{11}}+2^{b_{12}}+\cdots)1 + (2^{b_{31}}+2^{b_{32}}+\cdots)3 + \cdots$.

Now just get rid of the brackets, and note that all terms are distinct. (Why?)

E.g. for $20 = 5+3+3+3+1+1+1+1+1+1$, which is a partition of $20$ into odd parts, we do
$20 = (1)5 + (3)3 + (6)1$
$20 = (1)5 + (2+1)3 + (4+2)1$, so you get the partition
$20 = 5 + 6 + 3 + 4 + 2$ in which all parts are distinct.

Distinct parts -> Odd parts

Given a partition into distinct parts, we can write each part as a power of 2 multiplied by an odd number, and collect the coefficients of each odd number, and write the odd number those many times, to get a partition into odd parts.

So for example with $20 = 5+6+3+4+2$ which is a partition of $20$ into distinct parts, we write $20 = 5 + (2)3 + 3 + (4)1 + (2)1$, and then collect coefficients of the odd numbers $5$, $3$ and $1$:
$20 = 5 + (2+1)3 + (4+2)1$
$20 = 5+3+3+3+1+1+1+1+1+1$, which was our original odd partition.

Aside: you asked about the bijective proof, but I cannot resist mentioning that when Euler proved this theorem about partitions, it was with a proof that used generating functions. (When you understand both, maybe you can think about whether this proof is related to the bijective proof.)

Sketch: Let $D(n)$ denote the number of partitions into distinct parts, and $O(n)$ denote the number of partitions into odd parts. Then we have:

$$ \begin{align} \sum_{n\ge0}D(n)x^n &= (1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)\cdots \\ &= \frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^6}{1-x^3}\frac{1-x^8}{1-x^4}\frac{1-x^{10}}{1-x^5}\cdots \\ &= \frac{1}{(1-x)(1-x^3)(1-x^5)\cdots} \\ &= (1+x+x^{1+1}+\cdots)(1+x^3+x^{3+3}+\cdots)(1+x^5+x^{5+5}+\cdots) \\ &= \sum_{n\ge0}O(n)x^n \end{align} $$ which proves the theorem.