Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
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. –  Alex M Nov 11 '11 at 5:30
    
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! –  Bruno Joyal Nov 11 '11 at 5:36
    
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 –  Alex M Nov 11 '11 at 5:39
    
Sorry for this. I shouldn't post when I'm so tired. Here's something you might like better (if only because it works ;)). –  Bruno Joyal Nov 11 '11 at 5:47
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.