Partition ordering

[Richard Guy]

I doubt if you'll achieve consistency.  The `natural' way
is by partitioning!

xxxxxxxxx  xxxxxxxx  xxxxxxx  xxxxxxx  xxxxxx  xxxxxx  xxxxxx
            x         xx       x        xxx     xx      x
                               x                x       x
                                                        x

xxxxx  xxxxx  xxxxx  xxxxx  xxxxx  xxxx  xxxx  xxxx  xxxx
xxxx   xxx    xx     xx     x      xxxx  xxx   xxx   xx
        x      xx     x      x      x     xx    x     xx
                      x      x                  x     x
                             x

xxxx  xxxx  xxx  xxx  xxx  xxx  xxx  xxx  xxx  xx  xx  xx  xx  x
xx    x     xxx  xxx  xxx  xx   xx   xx   x    xx  xx  xx  x   x
x     x     xxx  xx   x    xx   xx   x    x    xx  xx  x   x   x
x     x          x    x    xx   x    x    x    xx  x   x   x   x
x     x               x         x    x    x    x   x   x   x   x
       x                              x    x        x   x   x   x
                                           x            x   x   x
R.                                                         x   x
                                                                x
On Wed, 11 Jan 2006, Marc LeBrun wrote:

> A&S in my 1970s vintage paperback "ninth Dover printing" (well, the back 
> cover does say "A DOVER EDITION DESIGNED FOR YEARS OF USE!") list partitions 
> starting on page 831 (maybe they've changed how they do it since then).
>
> They explicitly group them by length and then (it appears) lexicographically 
> within each group.  By the way, A&S notates the parts in ascending order 
> using exponents.
>
> In this ordering, 1,4^2 comes before 2^2,5 (144 < 225).  Here's the way A&S 
> lists the 30 partitions of 9:
>
> 9
> 18
> 27
> 36
> 45
> 117
> 126
> 135
> 144
> 225
> 234
> 333
> 1116
> 1125
> 1134
> 1224
> 1233
> 2223
> 11115
> 11124
> 11133
> 11223
> 12222
> 11114
> 111123
> 111222
> 1111113
> 1111122
> 11111112
> 111111111
>
> (By the way, each entry is accompanied by 3 "multinomial coefficients"--are 
> these in the OEIS?  The M1 values for the p(9) partitions above starts 
> 1,9,36,84,126,72,252,504,630,756,1260,1680... alas I daren't take time to 
> check right now).
>
>
> Now having said all that, I wonder what is the purpose?  I suppose there's 
> some value in some degree of standardization, for instance in comments and 
> examples, but surely there are perfectly good motivations to sometimes use 
> differing orders?  Also, since the OEIS tends to favor infinite sequences, 
> the question of how the partitions for different n can be serialized is 
> germane.  The obvious order is to just concatenate them, but there are 
> doubtless sometimes valid reasons to mix them up differently.
>
> For example here's a way to map integers 1-to-1 to partitions in a "crazy" 
> order: factor n, take the (finite) tuple of exponents, add 1 to the first, 
> use the rest as successive differences between parts, and finally subtract 1 
> from the last part:
>
> 2 -> [1]           -> 1
> 3 -> [0,1]         -> 11
> 4 -> [2]           -> 2
> 5 -> [0,0,1]       -> 111
> 6 -> [1,1]         -> 22
> 7 -> [0,0,0,1]     -> 1111
> 8 -> [3]           -> 3
> 9 -> [0,2]         -> 12
> 10 -> [1,0,1]       -> 222
> 11 -> [0,0,0,0,1]   -> 11111
> 12 -> [2,1]         -> 33
> 13 -> [0,0,0,0,0,1] -> 111111
> 14 -> [1,0,0,1]     -> 2222
> 15 -> [0,1,0,1]     -> 1222
> 16 -> [4]           -> 4
>
> and so on.  The powers of 2 map to the singleton partitions, primes to all 
> ones, etc.  The inverse of course takes partitions to integers, so each of 
> your three orderings maps back to a sequence (in fact a permutation of 
> integers)--are they in the OEIS?  (If they are we might use their A-numbers 
> to refer to them, rather than resorting to allusions to authors of reference 
> books or software "product placements").
>
> And there are many more games: adding partitions elementwise induces an 
> exotic binary operator on integers; its table can be serialized into the 
> OEIS, etc etc.
>
>
> So I guess the point of all this (assuming there is one beyond excess 
> caffeination) is to ask: what difference does it make which partition 
> convention any given instance adopts?  Or am I completely missing the point?
>
>