First, denote by $p_E(n)$ be the number of partitions of $n$ with an even number of parts, and let $p_O(n)$ be those with an odd number of parts. Moreover, let $p_{DO}(x)$ be the number of partitions of $n$ whose parts are distinct and odd. Finally, let $c(n)$ be the number of partitions of $n$ which are conjugate to themselves.
With this notation, why does $c(n)=p_{DO}(n)=(-1)^n(p_E(n)-p_O(n))$?
Best Answer
For the first equality, take the Young diagram of a self-conjugate partition and break it into hooks with a diagonal square as corner; their sizes form a partition of $n$ into distinct odd parts, and the inverse operation is obvious.
For the second equality, consider the following involution to match any partition of $n$ in the subset $S=p(n)\setminus p_{DO}(n)$ of partitions that are not into distinct odd parts, with another element of $S$ with the opposite parity of its number of its parts. For $\lambda\in S$, test the odd numbers $m=1,3,5,\ldots$ in order, considering the set of parts of $\lambda$ of the form $2^km$ with $k\in\mathbf N$. If the set is either empty or consists of a single part $m$, move on to the next odd number. Since $\lambda\in S$, there is some $m$ that is not skipped; stop at the smallest such $m$. Now take the maximal $k$ such that $\lambda$ has a part of size $2^km$. If this part is unique, then $k\neq0$ by the choice of $m$; break the part into two parts of size $2^{k-1}m$. Otherwise $\lambda$ has at least two such parts; glue them together to form a part of size $2^{k+1}m$. One readily checks that the partition $\mu$ so produced is in $S$, that this procedure is an involution on $S$, and that $\lambda,\mu$ always have opposite parities for the number of their parts.
So the elements of $S$ together produce a null contribution to $p_E(n)-p_O(n)$. It remains to show that each element of $p_{DO}(n)$ contributes $(-1)^n$ to $p_E(n)-p_O(n)$. But it is obvious (by adding up parts modulo $2$) that the parity of the number of parts of any partition in $P_{DO}(n)$ is the same as that of $n$, which settles this point.