[seqfan] Partitions orderings & encodings. Was: A possible new Keyword

Antti Karttunen antti.karttunen at gmail.com
Thu Sep 24 23:16:47 CEST 2015

On Thu, Sep 24, 2015 at 11:37 PM,  <seqfan-request at list.seqfan.eu> wrote:
> Message: 9
> Date: Thu, 24 Sep 2015 15:26:25 -0400
> From: Max Alekseyev <maxale at gmail.com>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] Re: A possible new Keyword
> Message-ID:
>         <CAJkPp5N8C661DUqJn6ph8FYNzF+95rMjC0pa+pT=abBWq20bnQ at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
> I'd rather say that it is possible to enumerate partitions this way (not
> that it is based on an ordering of the partitions).
> Also, this is very different from other ordering of partitions, which
> iterate over partitions of a fixed number first.

But in compensation we get a lots of already-submitted "useful tools"
and other "magic for free", whenever we use for any combinatorial
structure an encoding system which is based on some natural
isomorphism with the prime factorization of n (or any other
fundamental property of natural numbers, like e.g. their binary or
factorial expansion), avoiding the need to set up clumsy ranking and
unranking functions.

E.g. "partition conjugation" in https://oeis.org/A122111 for which I
found the most simple formula just as:
 a(1) = 1; a(n) = A105560(n) * a(A064989(n)).
Here A105560(n) = prime(bigomega(n)) and A064989(n) shifts the prime
factorization of n one step towards smaller primes, deleting any 2's

Also, the same system works with polynomials with nonnegative integer
coefficients very nicely, as I wrote in

For this specific prime factorization encoding, some operations acting
on partitions might actually provide some interesting problems to the
OEIS number theoreticians. Similarly with Matula-Goebel encodings for
rooted nonoriented general trees, see e.g. many sequences submitted by
Emeric Deutsch on that topic.



> Regards,
> Max
> On Thu, Sep 24, 2015 at 2:49 PM, Frank Adams-Watters <franktaw at netscape.net>
> wrote:
>> Note that while you can do this without thinking of partitions, it is in
>> fact based on an ordering of the partitions: A112798.
>> Franklin T. Adams-Watters

More information about the SeqFan mailing list