Integer partitions with restrictions for elements 
Possible Duplicate:
Same number of partitions of a certain type? 


Prove that the number of partitions of $n$ without elements divisible by $4$, is equal to the number of partitions of $n$ where each element appears at most $3$ times.

Don't know how to approach. Generating functions, Ferrers diagrams don't help. Seems very hard.
 A: Here’s a combinatorial argument. It can easily be adapted to show that the number of partitions of $[n]$ into parts that are not multiples of $d$ is equal to the number of partitions of $[n]$ in which each part has fewer than $d$ copies.
Let $\lambda$ be a partition of $[n]$ into parts that are not multiples of $4$, with part $k$ occurring $r_k$ times. If $k\ge 1$ and $\lambda$ does not have a part $k$, then $r_k=0$; in particular, $r_k=0$ whenever $4\mid k$. Each $r_k$ has a unique base four representation
$$r_k=\sum_{i\ge 0}a_k(i)4^i,\qquad a_k(i)\in\{0,1,2,3\}\;,$$
and
$$n=\sum_{k\ge 1}kr_k=\sum_{k\ge 1}\sum_{i\ge 0}a_k(i)4^ik\;.\tag{1}$$
Construct a partition $\mu$ as follows: for each $k$ appearing in $\lambda$ and each $i\ge 0$, $\mu$ has $a_k(i)$ parts $4^ik$. It follows from $(1)$ that $\mu$ is a partition of $[n]$. Moreover, $4^{i_1}k_1=4^{i_2}k_2$ iff $\langle i_1,k_1\rangle=\langle i_2,k_2\rangle$, since the parts $k$ of $\lambda$ are not divisible by $4$, and each $a_k(i)\le 3$, so $\mu$ has at most $3$ copies of each part. Clearly the map $\lambda\mapsto\mu$ is injective.
Conversely, if $\mu$ is a partition of $[n]$ that has at most $3$ copies of each part, let $p_1,\dots,p_m$ be the distinct parts of $\mu$. For $j=1,\dots,m$ let $p_j=4^{i_j}k_j$, where $4\nmid k(j)$; this factorization is unique. If $p_j$ occurs $r_j$ times in $\mu$, $$n=\sum_{j=1}^mr_j4^{i_j}k_j\;.$$
Let $K=\{k_j:j=1,\dots,m\}$. For each $k\in K$ let $$s_k=\sum_{k_j=k}r_j4^{i_j}\;,$$ and let $\lambda$ be the partition of $[n]$ with $s_k$ copies of $k$ for $k\in K$; clearly no part of $\lambda$ is a multiple of $4$, and it’s not hard to see that the map $\mu\mapsto\lambda$ is the inverse of the map $\lambda\mapsto\mu$ defined in the first paragraph. Thus, these maps are bijections establishing the desired result.
And here’s a generating function proof, arranged a little differently from svenkatr’s.
Let $f(x)$ be the generating function for the number of partitions with no multiple of $4$; then
$$f(x)=\prod_{4\nmid n\ge 1}\sum_{k\ge 0}x^{kn}=\prod_{4\nmid n\ge 1}\frac1{1-x^n}\;.$$
Let $g(x)$ be the generating function for partitions having at most $3$ copies of each part;
$$g(x)=\prod_{n\ge 1}\left(1+x^n+x^{2n}+x^{3n}\right)\;.$$
Then
$$\begin{align*}
g(x)\prod_{n\ge 1}(1-x^n)&=\prod_{n\ge 1}\left((1-x^n)\left(1+x^n+x^{2n}+x^{3n}\right)\right)\\
&=\prod_{n\ge 1}\left(1-x^{4n}\right)\\
&=\frac{\prod\limits_{n\ge 1}\left(1-x^n\right)}{\prod\limits_{4\nmid n\ge 1}(1-x^n)}\\
&=\prod_{4\nmid n\ge 1}\frac1{1-x^n}\prod_{n\ge 1}(1-x^n)\\
&=f(x)\prod_{n\ge 1}(1-x^n)\;,
\end{align*}$$
so $g(x)=f(x)$.
A: You can prove this using generating functions. Here's the idea (you should be able to fill in details).
How would you count the number of partitions of $n$ where each element appears at most 3 times? 
This would be the coefficient of $x^n$ in the polynomial $(1+x+x^2+x^3)(1+x^2+x^4+x^6)\ldots(1+x^n+x^{2n}+x^{3n})$. In other words, it is the coefficient of $x^n$ in $\prod_{i=1}^n (1+x^i+x^{2i}+x^{3i})$.
You can simply the expression as follows
\begin{equation}
\prod_{i=1}^n (1+x^i+x^{2i}+x^{3i}) = \prod_{i=1}^n \frac{x^{4i}-1}{x^i-1}
\end{equation}
Consider the right hand side of the above equation. Can you do a telescoping cancellation to prove your result? The numerator terms will cancel out every fourth denominator term until you run out of denominator terms.
