Bijective proof for a partition identity

Question

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.

Answer 1

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.

Answer 2

The answer is yes, there is a combinatorial proof, and both Sam's and Fёdor's proofs work. However, this is a really old result and a combinatorial proof is old. Here is the reference:

H. Gupta, Combinatorial proof of a theorem on partitions into an even or odd number of parts, J. Combin. Theory Ser. A, 21 (1976), no. 1, 100–103.

In general, you can find all of this in my survey. This particular problem is §3.2.4. This result goes back to Glaisher (1876), and the reference to Gupta is [79] given in the remarks at the end. You would need to also use an obvious bijection in §2.1.5 which is the first step in Sam's answer. According to Sylvester this is due to Durfee.

Answer 3

There's a well-known bijective proof that the number of self-conjugate partitions of $n$ is the same as the number of partitions of $n$ into distinct odd parts (see https://en.wikipedia.org/wiki/Partition_(number_theory)#Conjugate_and_self-conjugate_partitions).

Now we can define a sign reversing involution which proves that the number of partitions of $n$ with an even number of even parts minus the number of partitions with an odd number of even parts is the number of partitions into distinct odd parts, as follows.

Find the smallest $i$ such that either $2i$ is a part of $\lambda$ or we have a repeated $i$ part. If it's a repeated part of $i$, put two of those parts together to make an even part of $2i$. If it's an even part of $2i$, break it into two repeated parts of $i$. If we have a repeated part of $i$ and a part of size $2i$ then by fiat we prefer to break the $2i$ apart when we have an odd number of $2i$'s and prefer to put the $i$'s together when we have an even number of $2i$'s. This will change the parity of the number of even parts, except when we can't do anything: when we cannot find either a repeated part or an even part, and hence have a partition into distinct odd parts.