Assume that the following generating function equation is correct, prove the following statement: $\Pi_{i=1}^{\infty} (1+x^{3i})\Pi_{j=1}^{\infty} (1-x^{6j+3})=1$ Statement: The number of partitions of $n$ to numbers not of the form $6k+1$ or $6k-1$ is equal to the number of partitions of $n$ in which each summand appears at least twice. (10 points) Proposed by Morteza Saghafian
Problem
Source: Iran 3rd round 2013- Combinatorics exam problem 1
Tags: function, combinatorics unsolved, combinatorics
Naysh
26.09.2014 05:50
So the given identity is really just difference of squares...
First, the given identity can be written as \[\displaystyle \prod_{j=1}^{\infty}\dfrac{1}{\left(1+x^{3j}\right)}=\prod_{j=1}^{\infty}\left(1-x^{6j+3}\right).\]
Now, the number of partitions of an integer $n$ where each summand appears at least twice has generating function \[f(x)=\prod_{j=1}^{\infty}\left(1+\dfrac{x^{2j}}{1-x^j}\right) = \prod_{j=1}^{\infty}\dfrac{1-x^j+x^{2j}}{1-x^j}=\prod_{j=1}^{\infty}\dfrac{1+x^{3j}}{1-x^{2j}}.\]
The number of partitions of an integer $n$ where no part is $\equiv\pm 1\bmod 6$ is \[g(x)=\prod_{j=1}\dfrac{1}{1-x^j}\cdot\left(\prod_{a\equiv\pm 1\bmod 6}(1-x^a)\right).\]
It suffices to prove that $f(x)=g(x)$.
However, \[f(x)=g(x) \Longleftrightarrow\prod_{j=1}^{\infty}\dfrac{1+x^{3j}}{1-x^{2j}}=\prod_{j=1}\dfrac{1}{1-x^j}\cdot\left(\prod_{a\equiv\pm 1\bmod 6}(1-x^a)\right)\Longleftrightarrow\] \[\Longleftrightarrow\prod_{j=1}^{\infty}\dfrac{1}{1-x^{2j}} = \prod_{j=1}\dfrac{1}{(1-x^j)(1+x^{3j})}\cdot\left(\prod_{a\equiv\pm 1\bmod 6}(1-x^a)\right)\] and \[\prod_{j=1}\dfrac{1}{(1-x^j)(1+x^{3j})}\cdot \prod_{a\equiv\pm 1\bmod 6}(1-x^a)=\prod_{j=1}\dfrac{1}{1-x^j}\cdot\prod_{a\equiv\pm 1, 3\bmod 6}(1-x^a)\] by the given identity.
However, \[\prod_{j=1}\dfrac{1}{1-x^j}\cdot\prod_{a\equiv\pm 1, 3\bmod 6}(1-x^a)=\prod_{a\equiv 0, \pm 2\bmod 6}\dfrac{1}{1-x^a} = \prod_{j=1}\dfrac{1}{1-x^{2j}}.\]
Thus $f(x)=g(x)$, and the desired result follows.