# number of different kinds of partitions of $n$ are the same

I want to prove that:

The number of partitions of $n$ into parts congruent to $1$ or $5$ ($\text{mod}$ 6) equals number of partitions of $n$ into distinct parts all congruent to $1$ or $2$ ($\text{mod}$ 3).

Is there a way to prove this using the well known Mobius inversion formula? I have been trying to establish a bijection between the set of partitions of $n$ of the first kind and the set of partitions of $n$ of the latter kind, but it is very difficult to establish uniqueness. Any help is appreciated. Thank you.

## 1 Answer

Once approach is to use the generating functions. Let $S_1, S_2$ denote the sets $\{m \in \mathbb{N} : m \equiv 1,2 \pmod 3\}$ and $\{m \in \mathbb{N} : m \equiv 1,5 \pmod 6\}$. If $p_{S}(n)$ denotes the number of partitions of $n$ into elements of $S$ and $\overline{p_S}(n)$ denotes the number of partitions of $n$ into distinct elements of $S$, then as formal power series $$\sum_{n=0}^{\infty}\overline{p_{S_1}}(n)q^n = \prod_{j=0}^{\infty}(1 + q^{3j + 1})(1 + q^{3j + 2})$$ and $$\sum_{n=0}^{\infty}p_{S_2}(n)q^n = \prod_{j=0}^{\infty}\frac{1}{(1 - q^{6j + 1})(1 - q^{6j + 5})}.$$ We have \begin{equation*} \begin{aligned} &\mathrel{\phantom{=}}\prod_{j=0}^{\infty}(1 + q^{3j + 1})(1 + q^{3j + 2}) \\ &= \prod_{j=0}^{\infty}\frac{(1 - q^{6j + 2})(1 - q^{6j + 4})}{(1 - q^{3j + 1})(1 - q^{3j + 2})} \\ &= \prod_{j=0}^{\infty}\frac{(1 - q^{6j + 2})(1 -q^{6j+ 4})}{(1 - q^{6j + 1})(1 - q^{6j + 4})(1 - q^{6j + 2})(q - q^{6j + 5})} \\ &= \prod_{j=0}^{\infty}\frac{1}{(1 - q^{6j + 1})(1 - q^{6j + 5})}. \end{aligned} \end{equation*} thus $$\overline{p_{S_1}}(n) = p_{S_2}(n).$$ Here the second line follows from the difference of two squares identity and the third line follows by noting that $\{m \in \mathbb{N} : m \equiv 1,2 \pmod 3\} = \{m \in \mathbb{N} : m \equiv 1,2,4,6 \pmod 6\}$.

• How did you know that $\bar{p_{S_1}}$ equals the first product? – Ana Oct 11 '16 at 1:21
• We see that $$\prod_{j=0}^{\infty}(1 + q^{3n + 1})(1 + q^{3n + 2}) = \prod_{j \equiv 1 \pmod 3}(1 + q^j)\prod_{j \equiv 2 \pmod 3}(1 + q^j).$$ The coefficient $a(n)$ of $q^n$ in the expansion of the above product is the number of ways to multiply out finitely many terms $q^{a_1},\ldots,q^{a_s},q^{b_1},\ldots,q^{b_r}$ with $a_1 + \cdots + a_s + b_1 + \cdots + b_r = n$, where the $a_i \equiv 1 \pmod 3$ and $b_i \equiv 2 \pmod 3$ are distinct, hence $a(n) = \overline{p_{S_1}}(n)$. – Ethan Alwaise Oct 11 '16 at 4:37