Problem
COM-B2-M03-P016 Distinct and Odd Parts
Prove that the number of partitions of \(n\) into distinct parts equals the number of partitions of \(n\) into odd parts.
Write each part as \(2^s\cdot q\), where \(q\) is odd.
From a partition into odd parts, group equal odd parts \(q\). If \(q\) appears \(m\) times, write \(m\) in binary: \(m=\sum 2^s\). Replace these \(m\) copies of \(q\) by parts \(2^s q\). For each \(q\), the powers \(2^s q\) are distinct, and different odd \(q\)'s give different parts. Thus we get a partition into distinct parts.
Conversely, write each distinct part uniquely as \(2^s q\), with \(q\) odd, and replace it by \(2^s\) copies of \(q\). This gives a partition into odd parts. The two operations are inverse.
This is Glaisher's strong bijection; well suited for Book 2.