[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
present.
Also, the same system works with polynomials with nonnegative integer
coefficients very nicely, as I wrote in
http://list.seqfan.eu/pipermail/seqfan/2015-August/015155.html
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.
Best,
Antti
>
> 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