Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

marked as duplicate by Marc van Leeuwen, William, tomasz, Chris Eagle, Nate Eldredge Oct 6 '12 at 16:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2 Answers

up vote 0 down vote accepted

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\}\;,$$


$$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)\;.$$


$$\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)$.

share|improve this answer
As always great answer. Thank you so much! –  ray Aug 25 '12 at 19:01
add comment

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.

share|improve this answer
ok, so consider $n=4$, then we have generating function $\frac{x^4-1}{x-1}\frac{x^8-1}{x^2-1}\frac{x^{12}-1}{x^3-1}\frac{x^{16}-1}{x^4-1‌​}=\frac{x^8-1}{x^2-1}\frac{x^{12}-1}{x^3-1}\frac{x^{16}-1}{x-1}$, but I don't see here generating function for partitions without elements divisible by $4$ - I don't even know how would it look like. –  ray Aug 25 '12 at 8:45
Besides, I don't know if it's clear but these are partitions, so $6=1+1+1+1+2$ is ok for second (without elements divisble by $4$), but $6=2+4$ not, because it has element divisible by $4$. –  ray Aug 25 '12 at 8:53
In the case where $n=4$, you don't have the $\frac{1}{x^4-1}$ term in the denominator. This means that the element 4 and its multiples are excluded from the partition. You don't have to worry about the $x^8-1$ and higher terms in the numerator because they don't contribute to the coefficient of $x^4$ in the expanded version of the polynomial. –  svenkatr Aug 25 '12 at 19:07
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.