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?
Proving that exactly half the partitions of $n$ into powers of 2 have an even number of parts
2 Answers
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
$$P=\prod_{n=1}^\infty(1+x^{2^n})^{-1},$$
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.
-
0I'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. – 2011-11-11
-
0You'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! – 2011-11-11
-
0I'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 – 2011-11-11
-
0Sorry for this. I shouldn't post when I'm so tired. Here's something you might like better (if only because it works ;)). – 2011-11-11
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.