# Partition Proving

Let $A=\{2,6,10,14,\ldots\}$ be the set of integers that are twice an odd number.

Prove that, for every positive integer $n$, the number of partitions of $n$ in which no odd number appears more than once is equal to the number of partitions of $n$ containing no element of $A$.

For example, for $n=6$, the partitions of the first type are $$6,~~~5+1,~~~4+2,~~~3+2+1,~~~2+2+2,$$ and the partitions of the second type are $$5+1,~~~4+1+1,~~~3+3,~~~3+1+1+1,~~~1+1+1+1+1+1,$$ and there are $5$ of each type.

On first thought, my mind is blank. I simply do not know how to approach this problem. Solutions are greatly appreciated. Thanks in advance!

• I'd guess you could show the generating functions of the two are the same. – Thomas Andrews Nov 1 '16 at 23:54

HINT: Let $\mathscr{P}_0(n)$ be the set of partitions of $n$ in which no odd number appears more than once, and let $\mathscr{P}_1(n)$ be the set of partitions of $n$ containing no element of $A$. If $\lambda\in\mathscr{P}_0$, let $\hat\lambda$ be the partition of $n$ obtained by splitting each member of $\lambda$ that is in $A$ into two halves and leaving all other members as they are. For instance, if $\lambda$ is $4+2$, then $\hat\lambda$ is $4+1+1$. This clearly maps $\mathscr{P}_0(n)$ into $\mathscr{P}_1(n)$. I leave it to you to show that the map is actually a bijection. It’s pretty clearly injective, but you may have to think a little to see just what its inverse is.

For $n=6$ the correspondence is:

\begin{align*} 6&\leftrightarrow 3+3\\ 5+1&\leftrightarrow 5+1\\ 4+2&\leftrightarrow 4+1+1\\ 3+2+1&\leftrightarrow 3+1+1+1\\ 2+2+2&\leftrightarrow 1+1+1+1+1+1 \end{align*}

• Wow! I can't believe I actually missed that when I first read the problem! +1 Bravo on the creative thinking! – Dreamer Nov 2 '16 at 1:03

Let $f(n)$ be the partitions of $n$ with at most one occurrence of each odd number, and $F(z)=\sum_{n} f(n)z^n$.

Then \begin{align}F(z) &= (1+z)(1+z^2+z^4+\cdots)(1+z^3)(1+z^4+z^8+\cdots)\cdots \\&=\frac{(1+z)(1+z^3)(1+z^5)\cdots}{(1-z^2)(1-z^4)(1-z^6)\cdots} \end{align}

Now pair off the terms $\frac{1+z^{2k+1}}{1-z^{4k+2}}=\frac{1}{1-z^{2k+1}}$, and you get:

$$\prod_{j\notin A}\frac{1}{1-z^j}$$

And this expands to give you the generating function for counting partitions of $n$ with no instance from $A$.