Could you help me how to prove that exactly half the partitions of $n$ into powers of 2 have an even number of parts, please?


Let's go with a generating function proof since you're into those!

Consider the product

$$P=\prod_{n=0}^\infty\sum_{j=0}^\infty x^{2^nj}.$$

The coefficient of $x^m$ in this product is the number of partitions of $m$ into powers of two. If we modify it slightly by writing

$$P=\prod_{n=0}^\infty\sum_{j=0}^\infty (-1)^jx^{2^nj},$$

then each partition is given the weight $\pm 1$ according to whether the number of its parts is odd or even. Now of course this product is simply


which, by my solution to your other problem, is equal to $1-x$. Thus for $m=0$ and $m=1$, there are respectively $1$ more and $1$ less partitions of $m$ into an even number of parts as there are into an odd number of parts; for all other $m$, there are equally many.

  • $\begingroup$ I'm not understanding the application, for example, if we take $n=6$ and the partition $2,4$ then if we add together these two elements we have 6 but this isn't a power of two. $\endgroup$ – Mec Nov 11 '11 at 5:30
  • $\begingroup$ You're absolutely right, thank you. I actually had the correct solution at first, but then I wrote a bunch of nonsense instead. It works now! $\endgroup$ – Bruno Joyal Nov 11 '11 at 5:36
  • $\begingroup$ I'm not sure this is a bijection. Take $n=7$ and the partition 1,2,4 then this isn't the image of a partition in two parts thru your application $\endgroup$ – Mec Nov 11 '11 at 5:39
  • $\begingroup$ Sorry for this. I shouldn't post when I'm so tired. Here's something you might like better (if only because it works ;)). $\endgroup$ – Bruno Joyal Nov 11 '11 at 5:47

Let $S_e$ be the set of even partitions and $S_o$ the set of odd. Take any partition $s$ of $S_e$.

Let $2^r$ be the highest power of $2$ in $s$. If $s$ contains a single $2^r$ write $s = 2^r + p$ for remainder partition $p$ and define $s' = 2^{r-1} + 2^{r-1} + p$ noting that the resulting odd partition contains more than one of it's highest power of $2$, being $2^{r-1}$.

Similarly, if $s$ contains multiple $2^r$ then write $s' = 2^{r+1} + p$, noting that the resulting odd partition contains only one of it's highest power $2$, being $2^{r+1}$. This defines a bijection.


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.