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

Question

This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give me an understandable explanation of the proof and let me know how I'd go about finding such a bijection.

Answer 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.