Integer partition generating functions problem

Question

This is a homework question so I'd prefer to not receive a full solution but rather a hint.

The question is that $r_3(n)$ denotes the number of partitions of an integer $n$ into parts that are not multiples of $3$ and $s_2(n)$ denotes the number of partitions of an integer $n$ in which there are not more than $2$ parts of the same size. I have to prove that $r_3(n)=s_2(n)$ for all $n \geq 0$ by showing that the generating functions for the sequences $(r_3(n))_{n \geq0}$ and $(s_2(n))_{n\geq0}$ are the same.

I've shown that the generating function for $(r_3(n))_{n \geq 0}$ is $\prod_{n=1}^{\infty}\frac{1}{(1-x^{3n-2})(1-x^{3n-1})}=(1+x+x^2+...)(1+x^2+x^4+....)(1+x^4+x^8+...)(1+x^5+x^{10}+...)....$

and the generating function for $(s_2(n))_{n\geq0}$ is $\prod_{n=1}^{\infty}(1+x^{n}+x^{2n})=(1+x+x^2)(1+x^2+x^4)(1+x^3+x^6)(1+x^4+x^8)....$.

Are these generating functions correct? If yes, may I receive a hint as to how to show that they are equal?

Answer 1

Yes, both generating functions are correct. Here is your hint: $$1+x^n+(x^n)^2=\frac{1-(x^n)^3}{1-x^n}$$

Answer 2

You've correctly computed the generating function for $r_3(n)$ to be

$$ \big (1 + x + x^2 + x^3 + \ldots \big ) \big (1 + x^2 + (x^2)^2 + (x^2)^3) + \ldots \big ) \big (1 + x^4 + (x^4)^2 + (x^4)^3) + \ldots \big ) $$

which I prefer to write as

$$\prod_{3 \nmid k} \frac{1}{1-x^k}$$

particularly since (hint:) it makes it clear that this is

$$\frac{\prod_k \frac{1}{1-x^k}}{\prod_{3 \mid k} \frac{1}{1-x^k}}$$

---

Can you see how to relate that nested fraction formula to the generating function for $s_2(n)$, which you've also successfully computed to be

$$ \prod_k \big ( 1 + x^k + (x^k)^2 \big ) $$

I'll leave one more hint for this manipulation under the fold:

Try writing $P(x) = \prod_k \frac{1}{1-x^k}$. Then the generating function for $r_3(n)$ is $\frac{P(x)}{P(x^3)}$.

---

I hope this helps ^_^