Identity involving partitions of even and odd parts.

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))$?

Solution 1:

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.

Solution 2:

A sketch of a proof that $c(n)=p_{DO}(n)$ can be found here; it involves a simple manipulation of Ferrers diagrams. The rest seems easiest to do with generating functions.

First note that in

$$\prod_{k\ge 1}\frac1{1+x^k}=\prod_{k\ge 1}(1-x^k+x^{2k}-+\dots)\;,$$

the individual $x^n=x^{k_1}x^{k_2}\dots x^{k_m}$ terms are positive or negative according as $m$ is even or odd, and therefore

$$\prod_{k\ge 1}\frac1{1+x^k}=\sum_{k\ge 0}\big(p_E(k)-p_O(k)\big)x^k\,:$$

a partition $(k_1,k_2,\dots,k_m)$ is counted positively when $m$ is even and negatively when $m$ is odd.

Similarly, in

$$\prod_{k\ge 0}(1-x^{2k+1})$$

the $x^n$ terms are all of the form $x^{2k_1+1}x^{2k_2+1}\dots x^{2k_m+1}$, where the $k_i$ are distinct, and the term is positive for even $m$ and negative for odd $m$, so

$$\prod_{k\ge 0}(1-x^{2k+1})=\sum_{k\ge 0}(-1)^kp_{DO}(k)x^k\;.$$

If we can show that

$$\prod_{k\ge 0}(1-x^{2k+1})=\prod_{k\ge 1}\frac1{1+x^k}\;,\tag{1}$$

we’ll be able to conclude that $p_E(k)-p_O(k)=(-1)^kp_{DO}(k)$ and hence that $p_{DO}(k)=(-1)^k(p_E(k)-p_O(k))$.

To prove $(1)$, observe that

$$\begin{align*} \prod_{k\ge 1}\frac1{1+x^k}&=\prod_{k\ge 1}\frac{1-x^k}{1-x^{2k}}\\\\ &=\frac{\prod\limits_{k\ge 1}(1-x^k)}{\prod\limits_{k\ge 1}(1-x^{2k})}\\\\ &=\frac{\prod\limits_{k\ge 1}(1-x^{2k})\prod\limits_{k\ge 0}(1-x^{2k+1})}{\prod\limits_{k\ge 1}(1-x^{2k})}\\\\ &=\prod_{k\ge 0}(1-x^{2k+1})\;. \end{align*}$$