# Showing two generating functions to be equal

Let $\mathcal{A}$ be the set of partitions in which each part may occur 0, 1, 4, or 5 times and let $\mathcal{B}$ be the set of partitions which have no parts congruent to 2mod4, and in which parts divisible by four occur at most once each. Then for any $n \in \mathbb{N}$, I need to show that $|\mathcal{A}_n| = |\mathcal{B}_n|$. In other words, I need to show that the number of partitions in $\mathcal{A}$ of size n equals the number of partitions $\mathcal{B}$ of size n.

What I've done so far was the following. I've managed to derive both generating functions, namely:

$$\begin{equation*}\Phi_\mathcal{A} = \prod_{j=1}^{\infty}(1 + x^j + x^{4j} + x ^{5j})\end{equation*}$$

$$\begin{equation*}\Phi_\mathcal{B} = \prod_{j=1}^{\infty}(1 + x^{4j})\left(\frac{1}{1-x^{4j-3}}\right)\left(\frac{1}{1-x^{4j-1}}\right)\end{equation*}$$

Furthermore, in order to show that $|\mathcal{A}_n| = |\mathcal{B}_n|$ for any $n \in \mathbb{N}$, it suffices to show that the two generating functions are equal, $\Phi_\mathcal{A} = \Phi_\mathcal{B}$. However, I am unsure how to go about to manupulate them in order to show this final desired result. Any help would be appreciated.

Thanks!

-
Try using the Taylor series expansion for $\frac{1}{1-u}$ to simplify $\Phi_B$. en.wikipedia.org/wiki/… –  Austin Mohr Nov 13 '12 at 22:11
I've also noticed that $(1+x^j+x^{4j}+x^{5j})$ factors to $(1+x^j)(1+x^{4j})$. So it would seem to be that it would be sufficient to show that $(1+x^j)$ is equal to the product of the two fractional portions of $\Phi_\mathcal{B}$, which doesn't seem to be the case at all (even if one does consider the Taylor expansion)? –  Nizbel99 Nov 13 '12 at 22:33

Yes, your own observation nicely works. Start with ${\cal B}$.

First use the trick also mentioned in wikipedia (for partitions in odd parts) to show that

$\frac{1}{(1-x)(1-x^3)(1-x^5)(1-x^7)\dots} =$ $(1+x)(1+x^2)(1+x^3) \dots$; this is the product of the fractions of odd powers $\prod(\frac{1}{1-x^{4j-3}})(\frac{1}{1-x^{4j-1}})$.

Now you have to multiply that result with the multiples of $4$, i.e, $(1+x^4)(1+x^8)(1+x^{12}) \dots$, combining $(1+x^j)(1+x^{4j})$ -- here $(1+x^j)$ is a term from the previous computation and $(1+x^{4j})$ one of the multiples of $4$. Voila.

-
I looked at the article you mentioned, and I understand the trick with regards to the example on Wikipedia. However, I don't see how I would use it here. Could you please explain a little more? Say I consider $\frac{1}{1-x^{4j-3}}$, you're suggesting that I multiple top and bottom by $(1+x^4)(1+x^8)...$, but I don't see how that all cancels out with the other fractional portion to become $(1+x^j)$. –  Nizbel99 Nov 14 '12 at 1:05
I feel like I may be missing something obvious. –  Nizbel99 Nov 14 '12 at 1:10
OK. I tried to add some explanation where the factors are coming from. You take both $4j-3$ and $4j-1$ together, and you get all odd numbers, at least that seems to bother you? (But now I go to bed.) –  Hendrik Jan Nov 14 '12 at 1:30
Thanks! - I follow now :) –  Nizbel99 Nov 14 '12 at 1:58