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


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.

  • 1
    $\begingroup$ Nice; I’d not seen that argument before. $\endgroup$ – Brian M. Scott Dec 17 '11 at 12:53
  • $\begingroup$ @BrianM.Scott: And I had not seen the second equality before, I think. But this is really exercise grade. The idea of splitting/gluing should be obvious, and doing $n=4,5$ suffices to see how to proceed. $\endgroup$ – Marc van Leeuwen Dec 17 '11 at 13:32
  • $\begingroup$ Thank you Marc van Leeuwen and Brian M. Scott for answering my question. $\endgroup$ – seungyeon Dec 17 '11 at 17:40

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*}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.