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
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?