Partitions into distinct parts and into odd parts

Text

A theorem of Euler states that, for every $n$, the number $D(n)$ of partitions of $n$ into all distinct parts equals the number $O(n)$ of partitions of $n$ into all odd parts. Check it for $n=9$ by listing both families and finding the common value.

Solution

Distinct parts ($D(9)$): $9;\ 8{+}1;\ 7{+}2;\ 6{+}3;\ 5{+}4;\ 6{+}2{+}1;\ 5{+}3{+}1;\ 4{+}3{+}2 \quad\Rightarrow\ 8.$ Odd parts ($O(9)$): $9;\ 7{+}1{+}1;\ 5{+}3{+}1;\ 5{+}1{+}1{+}1{+}1;\ 3{+}3{+}3;\ 3{+}3{+}1{+}1{+}1;\ 3{+}1{\cdots}1;\ 1{+}\cdots{+}1 \quad\Rightarrow\ 8.$ Both give $\boxed{8}$ partitions, as predicted by Euler’s theorem.