: Distinct and Odd Partitions Puzzle : the
solution
: Let's write out the distinct and odd partitions
of 6 again:
: The Distinct Partitions
of 6:
: 6
: 5 1
: 4 2
: 3 2 1 
: The Odd Partitions
of 6:
: 5 1
: 3 3
: 3 1 1 1
: 1 1 1 1 1 1 1 
: I claim that {6} becomes {3 3}, {5 1} becomes
{5 1}, {4 2} becomes {1 1 1 1 1 1}
: and {3 2 1} becomes {3 1 1 1}, and vice versa. Do you see it
yet?
: Here's the bijection, described algorithmically:
: To map from a distinct to an odd partition, we
decompose each even number 'k'
: in the distinct partition into a pair of numbers k1 and k2,
where k1 = k2 (i.e. we
: divide k by 2). If these numbers are still even, then we repeat
the process ad
: infinitum until we are left with only odd numbers. A distinct
partition that is
: also an odd partition, we simply leave asis. Try this algorithm
with {4 2}.
: To map from an odd to a distinct partition, we
take the first pair of repeated
: values and add them. We continue this process moving from right
to left, until
: we have a distinct set. As above, an odd partition that is also
a distinct partition
: we leave asis. Try this approach with {1 1 1 1 1 1 }.
: Try it on a more complicated partition (thanks
to James Corey for correcting a mistake in this example):
: The Distinct Partitions
of 10:
: 10
: 9 1
: 8 2
: 7 3
: 7 2 1
: 6 4
: 6 3 1
: 5 4 1
: 5 3 2
: 4 3 2 1 
: The Odd Partitions
of 10:
: 9 1
: 7 3
: 7 1 1 1
: 5 5
: 5 3 1 1
: 5 1 1 1 1 1
: 3 3 3 1
: 3 3 1 1 1 1
: 3 1 1 1 1 1 1 1
: 1 1 1 1 1 1 1 1 1 1 1 
