Partition Identity – Bijective Proof

bijective-combinatoricsco.combinatoricspartitionsreference-requestsymmetric-groups

I came across the following cute fact about partitions:

\begin{align}
& |\{\lambda \vdash n \text{ with an even number of even parts}\}| \\[8pt]
& {} – |\{ \lambda \vdash n \text{ with an odd number of even parts}\}| \\[8pt]
= {} & |\{ \lambda \vdash n \text{ which are self-conjugate } (\text{i.e. } \lambda = \lambda^\top )\}|
\end{align}

I have a simple proof via the representation theory of $S_n$ — or really the result just fell out of a calculation I was doing. I was wondering if anyone knew a purely combinatorial bijective proof or had a reference for one.

Best Answer

Lemma. For $n>1$, the number of partitions of $n$ onto an even number of powers of 2 (here powers of 2 are 1,2,4,...) and the number of partitions of $n$ onto an odd number of powers of 2 are equal.

Proof. If $n$ is odd, we must have a part equal to 1, so subtract it and work with $n-1$ instead. If $n=2k$, then

  • $k=1$ is clear

  • $k>1$ and we consider only partitions without 1's: this is the same claim for $k$

  • $k>1$ and we consider partitions which contain 1's: this is the same claim for $2k-2$.

(This argument may be made more bijective if you prefer.)

Now we prove that the difference in LHS equals to the number of partitions to distinct odd parts (which, as Sam recalls, equals to the number of self-conjugate partitions by considering the hooks of diagonal boxes). Consider all parts of the form $r\cdot 2^i$, $i=0,1,2,\ldots$, $r$ is a fixed odd number. If we fix their sum, and it is greater than $r$, than by Lemma it may be achieved using odd and even number of parts by equally many ways. Since the number of odd parts has always the same parity, we use odd and even number of even parts equally often. So, if this happens at least for one odd $r$, we have a bijection between partitions with odd and even number of even parts. What remains? Exactly partitions onto distinct odd parts.

Related Question