Structure & Strangeness

 

: 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 as-is. 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 as-is. 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

 

 

: Creative :
.: Photography :.
.: Artistic :.
.: Blog :.
.: Thinking :.
.: Research :.

: Persona :
.: About :.
.: .plan :.
.: Vitae :.

: Website :
.: Search :.
.: Copyright :.
.: Sitemap :.
.: Links :.

© Aaron Clauset

updated 11.05.03