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!

  • $\begingroup$ I'd guess you could show the generating functions of the two are the same. $\endgroup$ – 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*}$$

  • $\begingroup$ Wow! I can't believe I actually missed that when I first read the problem! +1 Bravo on the creative thinking! $\endgroup$ – 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$.


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.