25
$\begingroup$

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.

$\endgroup$
5
  • $\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, 2011 at 15:37
  • 2
    $\begingroup$ Do you understand the illustrated folding and piling explanation over at Wikipedia? $\endgroup$
    – anon
    Aug 1, 2011 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, 2011 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, 2011 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$ Aug 1, 2011 at 16:21

1 Answer 1

50
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ Aside from the bijective , for the generating function solution you deserve +1000 ! $\endgroup$
    – JAN
    Jul 19, 2013 at 8:40
  • $\begingroup$ How do you get from the second equality to the third equality in the generating function argument? $\endgroup$ Mar 23, 2014 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$ Mar 23, 2014 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$
    – user632577
    Mar 11, 2019 at 15:50
  • 1
    $\begingroup$ @JAN $1000!>\sqrt{1000^{1000}}$ is a really big number. $\endgroup$ Jun 5, 2019 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.