1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How did you know that $\bar{p_{S_1}}$ equals the first product? $\endgroup$ – Ana Oct 11 '16 at 1:21
  • $\begingroup$ 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)$. $\endgroup$ – Ethan Alwaise Oct 11 '16 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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