Generating functions for partitions of n with an even number of parts and odd number of parts, and their difference.

Question

I've been trying to figure this out for more than 10 hours.

So far I have, for even number of partitions, $$P_e(x)=\sum_{k\ge1}(x^{2k}\prod_{i=1}^{2k}\frac{1}{1-x^i})$$ and for odd numbers $$P_o(x)=\sum_{k\ge1}(x^{2k-1}\prod_{i=1}^{2k-1}\frac{1}{1-x^i})$$ Hopefully you can see the direction I'm headed in. According the the problem, the difference of the two $$P_e(x) - P_o(x)$$ is supposed to equal $$\prod_{n\ge1}\frac{1}{1+x^n}$$

I have tried subtracting my results and cannot get anywhere. Can anyone shed some light on how to approach this problem?

Answer 1

You don’t need your expressions for $P_e(x)$ and $P_o(x)$; just expand

$$\prod_{k\ge 1}\frac1{1+x^k}=\prod_{k\ge 1}(1-x^k+x^{2k}-+\ldots\;,$$

and notice that the individual $x^n=x^{k_1}x^{k_2}\ldots x^{k_m}$ terms of the outer product are positive or negative according as $m$ is even or odd, so the coefficient of $x^k$ in

$$\prod_{k\ge 1}\frac1{1+x^k}$$

is the number of partitions of $k$ with an even number of parts minus the number with an odd number of parts.

You may find this question and its answers of interest; it goes beyond your present problem, but I shouldn’t be surprised if you found yourself dealing with the topic soon.

Answer 2

Let $X$ be a set and $\mathcal P(X)$ be the set of all subsets of $X$. Furthermore, let $$P=\mathcal P(\Bbb Z_{\ge0}\times\Bbb Z_{\ge0}),$$ which is the set of all subsets $\{(n_1,k_1),(n_2,k_2),...,(n_j,k_j)\}\subset\Bbb Z_{\ge0}\times\Bbb Z_{\ge0}$. Finally, for any $\pi=\{(n_i,k_i):i\in I\}\in P$, define $$||\pi||=\sum_{i\in I}n_ik_i.$$

Then for any uniformly convergent power series $f(q)=\sum_{n\ge0}a_nq^n$, we have

$$\begin{align} \prod_{k\ge1}f(q^k)&=\prod_{k\ge1}\left(\sum_{n\ge0}a_nq^{nk}\right)\\ &=\sum_{\pi\in P}\prod_{(n,k)\in\pi}a_nq^{nk}\\ &=\sum_{\pi\in P}q^{||\pi||}\prod_{(n,k)\in\pi}a_n\\ &=\sum_{N\ge0}q^{N}\sum_{\,\,\,\pi\in P\\ ||\pi||=N}\prod_{(n,k)\in\pi}a_n.\tag1 \end{align}$$ The takeaway fact here is that the sum $\displaystyle \sum_{\,\,\,\pi\in P\\ ||\pi||=N}$ is being taken over all partitions of $N$.

In our case, $$\prod_{k\ge1}\frac{1}{1+q^k}=\sum_{N\ge0}q^N\sum_{\,\,\,\pi\in P\\ ||\pi||=N}\prod_{(n,k)\in\pi}(-1)^n.$$ We can see that each partition $||\pi||=N$ can be re-written as $$||\pi||=n_1k_1+n_2k_2+...+n_jk_j=\underbrace{k_1+k_1+...+k_1}_{n_1\text{ times}}+...+\underbrace{k_j+k_j+...+k_j}_{n_j\text{ times}}.$$ So the total number of parts in the partition $||\pi||=N$ is given by the quantity $$\text{#}(\pi)=\sum_{(n,k)\in\pi}n=\sum_{i\in I}n_i.$$ Then we have $$\prod_{(n,k)\in\pi}(-1)^n=(-1)^{\text{#}(\pi)}.$$ So, given a partition $||\pi||=N$, if there is an even number of parts (that is, $\text{#}(\pi)$ is even) then $(-1)^{\text{#}(\pi)}=1$. Likewise, if $\text{#}(\pi)$ is odd $(-1)^{\text{#}(\pi)}=-1$. Summing over all partitions $||\pi||=N$, we get $$\begin{align} \sum_{||\pi||=N}(-1)^{\text{#}(\pi)}=&\text{# of partitions with an even number of parts}\\ &-\text{# of partitions with an odd number of parts}\\ =& p_e(N)-p_o(N). \end{align}$$ Therefore $$\prod_{k\ge1}\frac{1}{1+q^k}=\sum_{n\ge0}(p_e(n)-p_o(n))q^n.$$