This site is supported by donations to The OEIS Foundation.

User:Antti Karttunen/Mail by Marc LeBrun Re Partition ordering on SeqFan list posted 12 Jan 2006

From OeisWiki
Jump to: navigation, search
Return-Path: <seqfan-owner@ext.jussieu.fr>
Message-Id: <6.2.1.2.2.20060111202219.036d5a50@mail.well.com>
Date: Wed, 11 Jan 2006 23:16:20 -0800
To: franktaw@netscape.net
From: Marc LeBrun <mlb@fxpt.com>
Subject: Re: Partition ordering
Cc: seqfan@ext.jussieu.fr
In-Reply-To: <8C7E542BA5774C4-23F4-E34B@mblkn-m08.sysops.aol.com>
References: <8C7E542BA5774C4-23F4-E34B@mblkn-m08.sysops.aol.com>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed

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?