# Integer Partitions Formulas [duplicate]

Possible Duplicate:
Identity involving partitions of even and odd parts.

How would I go about to show the following: Let $pe(n)$ be the number of partitions of size n with an even number of parts and let $po(n)$ be the number of partitions of size n with an odd number of parts. If $od(n)$ is the number of partitions of size n with odd and distinct parts, show that for all $n$, $pe(n) - po(n) = (-1)^nod(n)$.

My idea was the following: Getting the generating functions for the 3 sets of partitions above, then try extracting the coefficient of $x^n$, denoted by $[x^n]$, then simply manipulate them to get the desired result. However, the generating functions are all of the form: $\prod_{i=1}^{\infty}\frac{1}{1-x^i}$ (generating function for the set of all partitions), and I have no idea how to extract the coefficients for such a function (and whether or not it's possible using relatively basic principles).

Can anyone point me in the right direction? I'm sure that there must be some better way to do this. Thanks!

-

## marked as duplicate by Brian M. Scott, Marc van Leeuwen, inactive... for now♦, Phira, J. M.Nov 11 '12 at 10:56

You’ll find two complete solutions at the older question, one with generating functions and one of a more combinatorial nature. – Brian M. Scott Nov 11 '12 at 6:44

There is actually a direct generating function for $p_e(n) - p_o(n)$. It is given by $$\prod_{n\ge1}\frac{1}{1 + x^n} = \sum_{n\ge0}(p_e(n)-p_o(n))x^n$$ Can you see why? (If you are familiar with a proof of Euler's pentagonal formula, then this should be somewhat familiar)
Similarly, there is a generating function for the number of partitions into odd distinct parts. It is given by $$\prod_{k\ge 0}\left(1+x^{2k+1}\right) = \sum_{n\ge 0}p_{od}(n)x^n$$ Now, every partition of an odd number into odd parts necessarily contains an odd number of terms. Every partition of an even number into odd parts necessarily contains an even number of terms. So if we modify the above slightly by introducing a negative sign, there will be no unwanted cancellation and the net effect is $$\prod_{k\ge 0}\left(1-x^{2k+1}\right) = \sum_{n\ge 0}(-1)^np_{od}(n)x^n$$ Your job now is to prove that the two generating functions are equal. Algebraic manipulations will be enough for this purpose, there is no need to extract the coefficients.
Euler's pentagonal formula is more or less irrelevant, there is just one step in there which is reminiscent of the first generating function. If you expand the first generating function, you have $$\prod_{k\ge 1}\left(1 - x^k + x^{2k} - x^{3k} + \cdots\right)$$ Every partition with an even number of parts contributes $+1$ to the coefficient of $x^n$ and every partition with an odd number of parts contributes a $-1$ to the coefficient. Can you see why we have then sum then? – EuYu Nov 11 '12 at 5:35