3
$\begingroup$

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.

2 Answers 2

2

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

  • 0
    As always great answer. $T$hank you so much!2012-08-25
1

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.

  • 0
    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.2012-08-25