Intuition for Euler's Partition Theorem Euler's Partition Theorem states the following:

Every number has as many integer partitions into odd parts as into distinct parts.

I played around with small examples (I wrote out the partitions into odd/distinct parts for integers 1 through 10), but can't develop an intuition for why this is true. Any help? 
 A: You can set up a one-to-one correspondence (aka a bijection) between the partitions of $N$ into odd parts and the partitions of $N$ into distinct parts. I will just illustrate with an example; I leave it to you to formalize it and verify that it works.
Here is one way to partition the number $N=863$ into odd parts: partition it into $22$ ones, $49$ threes, $48$ fives, $25$ sevens, and $31$ nines. From this we derive a partition of $863$ into distinct parts, as follows:
$863$
$=22\cdot1+49\cdot3+48\cdot5+25\cdot7+31\cdot9$
$=(16+4+2)\cdot1+(32+16+1)\cdot3+(32+16)\cdot5+(16+8+1)\cdot7+(16+8+4+2+1)\cdot9$
$=16\cdot1+4\cdot1+2\cdot1+32\cdot3+16\cdot3+1\cdot3+32\cdot5+16\cdot5+16\cdot7+8\cdot7+1\cdot7+16\cdot9+8\cdot9+4\cdot9+2\cdot9+1\cdot9$
$=16+4+2+96+48+3+160+80+112+56+7+144+72+36+18+9$
$=160+144+112+96+80+72+56+48+36+18+16+9+7+4+3+2$.
If we apply this procedure to the partitions of $7$ we get the following correspondence:
$7\ \to\ 7$
$5+1+1\ \to\ 5+2$
$3+3+1\ \to\ 6+1$
$3+1+1+1+1\ \to\ 4+3$
$1+1+1+1+1+1+1\ \to\ 4+2+1$
The relevant arithmetical facts here are unique factorization (every number factors uniquely into a power of $2$ and an odd number) and base $2$ notation (every number is uniquely expressible as a sum of distinct powers of $2$).
