[3.2] Exercise 20
Partition identities usually involve conditions on sizes of parts and on the number of parts. We have seen how these notions are connected by conjugation. Another common condition is that parts be distinct. Use conjugation to show that
\[
p(n \mid \text{distinct parts}) = p(n \mid \text{parts of every size from } 1 \text{ to the largest part}).
\]
For example, for \(n = 6\), the left-hand side counts the four partitions \(6, 5+1, 4+2, 3+2+1\) while the right-hand side counts the four partitions \(1+1+1+1+1+1\), \(2+1+1+1+1\), \(2+2+1+1\), \(3+2+1\)
Solution
Suppose we start with a partition of \(n\) with distinct parts meaning that each row has a distinct length. Moreover, rows get shorter as we go down so \(r_1 > r_2 > r_3 ... \cdots\). Then if we conjugate the partition, rows becomes columns. For example
Since all row lengths are distinct in the original partition, at most one row can end at any given column. Then when the rows are switched to columns, the column heights will decrease by exactly one or stay constant. Thus, every integer from \(1\) up to the largest column height occurs at least once.