Let $e(n)$ be the number of partitions of $n$ with even number of even parts and let $o(n)$ denote the number of partitions with odd number of even parts. In Enumerative Combinatorics 1, it is claimed that it is easy to see that $\sum_{n \geq 0} (e(n) - o(n)) x^n = \frac{1}{(1-x) \times (1+x^2) \times (1 - x^3 ) \times (1+x^4) \times ... }$. I have been racking my head over this for the past few hours, and I can't see any light.

I noticed, that $e(n) - o(n) = 2e(n) - p(n)$ where $p(n)$ is the number of partitions of $n$, so the above claim is equivalent to showing $\sum_{ n \geq 0} e(n)x^n = \frac{1}{2} \frac{1}{(1-x)(1-x^3)(1-x^5)...}( \frac{1}{(1-x^2)(1-x^4)....} + \frac{1}{(1+x^2)(1+x^4)........})$, and similarly, it is equivalent to $\sum_{ n \geq 0} o(n)x^n = \frac{1}{2} \frac{1}{(1-x)(1-x^3)(1-x^5)...}( \frac{1}{(1-x^2)(1-x^4)....} - \frac{1}{(1+x^2)(1+x^4)........})$, but these identities appear more difficult than the original one.

Any hints and suggestions appreciated.


Now, $$ \frac{1}{(1-x)(1+x^2)(1-x^3)\dots} $$

$$ = (1+x+x^2+\dots)(1-x^2+x^4-\dots)(1+x^3+x^6+\dots)(1-x^4+x^8-\dots)\dots $$

Consider a term which provides a negative coefficient to $x^n$

If we pick $x^{2n_2}$ from the second term, $x^{4n_4}$ from the fourth and so on,

The coefficient of $-1$ is $$(-1)^{n_2 + n_4 + \dots}$$

this will be negative if and only if $n_2 + n_4 + \dots$ is odd which comes from $o(n)$.

The positive ones come from $e(n)$.

Thus we must have that

$$\sum (e(n) - o(n))x^n = \frac{1}{(1-x)(1+x^2)(1-x^3)\dots}$$

  • $\begingroup$ very nice proof! $\endgroup$ – Arin Chaudhuri Sep 20 '10 at 4:13

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.