2
$\begingroup$

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!

  • 1
    You’ll find two com$p$lete solutions at the older question, one with generating functions and one of a more combinatorial nature.2012-11-11

1 Answers 1

4

A few hints to get you started.

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.

  • 0
    I'm trying to generate the generating function for $p_e(n)$ and $p_o(n)$, then subtract them from one another to see if I get the product you got.2012-11-11