This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give me an understandable explanation of the proof and let me know how I'd go about finding such a bijection.

  • $\begingroup$ So you have a collection of n objects and you want to divide them into k parts with amounts $x_1,x_2,...,x_k$, with $x_1+x_2+...+x_k=n$ ? Maybe if you gave us the link, we could help you better. $\endgroup$ – gary Aug 1 '11 at 15:37
  • 2
    $\begingroup$ Do you understand the illustrated folding and piling explanation over at Wikipedia? $\endgroup$ – anon Aug 1 '11 at 15:39
  • $\begingroup$ Who are you asking? Please remember my comment was re the question as posted originally, and not the question in its edited form. $\endgroup$ – gary Aug 1 '11 at 15:45
  • $\begingroup$ I'm sorry, I misinterpreted the question badly. I've undone the title. I now believe OP is talking about this. $\endgroup$ – anon Aug 1 '11 at 15:51
  • 1
    $\begingroup$ @rapidash: this would be a better question if you gave a specific bijective proof and told us where the explanation goes over your head. $\endgroup$ – Cheerful Parsnip Aug 1 '11 at 16:21

I'll give a sketch of the bijective proof; ask me if there's some part you don't understand and need fleshed out (or maybe someone else will post a detailed version).

The important idea is that every number can be expressed uniquely as a power of 2 multiplied by an odd number. (Divide the number repeatedly by 2 till you get an odd number.) For instance, $120 = 2^3 \times 15$ and $68 = 2^2 \times 17$ and $81 = 2^0 \times 81$.

Odd parts -> Distinct parts

Suppose you are given a partition of n into odd parts. Count the number of times each odd number occurs: suppose $1$ occurs $a_1$ times, similarly $3$ occurs $a_3$ times, etc. So $n = a_11 + a_33 + a_55 + \cdots$.

Now write each $a_i$ "in binary", i.e., as a sum of distinct powers of two. So you have $n = (2^{b_{11}}+2^{b_{12}}+\cdots)1 + (2^{b_{31}}+2^{b_{32}}+\cdots)3 + \cdots$.

Now just get rid of the brackets, and note that all terms are distinct. (Why?)

E.g. for $20 = 5+3+3+3+1+1+1+1+1+1$, which is a partition of $20$ into odd parts, we do
$20 = (1)5 + (3)3 + (6)1$
$20 = (1)5 + (2+1)3 + (4+2)1$, so you get the partition
$20 = 5 + 6 + 3 + 4 + 2$ in which all parts are distinct.

Distinct parts -> Odd parts

Given a partition into distinct parts, we can write each part as a power of 2 multiplied by an odd number, and collect the coefficients of each odd number, and write the odd number those many times, to get a partition into odd parts.

So for example with $20 = 5+6+3+4+2$ which is a partition of $20$ into distinct parts, we write $20 = 5 + (2)3 + 3 + (4)1 + (2)1$, and then collect coefficients of the odd numbers $5$, $3$ and $1$:
$20 = 5 + (2+1)3 + (4+2)1$
$20 = 5+3+3+3+1+1+1+1+1+1$, which was our original odd partition.

Aside: you asked about the bijective proof, but I cannot resist mentioning that when Euler proved this theorem about partitions, it was with a proof that used generating functions. (When you understand both, maybe you can think about whether this proof is related to the bijective proof.)

Sketch: Let $D(n)$ denote the number of partitions into distinct parts, and $O(n)$ denote the number of partitions into odd parts. Then we have:

$$ \begin{align} \sum_{n\ge0}D(n)x^n &= (1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)\cdots \\ &= \frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^6}{1-x^3}\frac{1-x^8}{1-x^4}\frac{1-x^{10}}{1-x^5}\cdots \\ &= \frac{1}{(1-x)(1-x^3)(1-x^5)\cdots} \\ &= (1+x+x^{1+1}+\cdots)(1+x^3+x^{3+3}+\cdots)(1+x^5+x^{5+5}+\cdots) \\ &= \sum_{n\ge0}O(n)x^n \end{align} $$ which proves the theorem.

  • 1
    $\begingroup$ Aside from the bijective , for the generating function solution you deserve +1000 ! $\endgroup$ – JAN Jul 19 '13 at 8:40
  • $\begingroup$ How do you get from the second equality to the third equality in the generating function argument? $\endgroup$ – Peter Olson Mar 23 '14 at 14:43
  • 1
    $\begingroup$ @PeterOlson: By cancelling the $(1-x^2), (1-x^4), (1-x^6), \dots, (1-x^{2k}), \dots$ factors that appear both in the numerator and in the denominator. $\endgroup$ – ShreevatsaR Mar 23 '14 at 14:54
  • $\begingroup$ Wow I just realized that the two proof are actually related, by $$\frac{1}{1-x^r}=(1+x^r)(1+x^{2r})(1+x^{4r})(1+x^{8r})\cdots$$ $\endgroup$ – Edward H Mar 11 '19 at 15:50
  • $\begingroup$ @JAN $1000!>\sqrt{1000^{1000}}$ is a really big number. $\endgroup$ – Dietrich Burde Jun 5 '19 at 19:37

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.