Partition Proving

Question

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!

Answer 1

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*}$$

Answer 2

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