[seqfan] Re: Permutations of the natural numbers - subcategories needed?

[Antti Karttunen]

(A couple of people replied to me privately. Please post valuable
ponderings to the list also!)

About automatic classification, pertaining especially to permutations of
natural numbers (I recall I posted this idea for the first time in the turn
of Millenium, and I still have an old Python-script somewhere):

If we search (from stripped.gz data for example) all such sequences where
all the numbers 2^k .. 2^(k+1)-1 occur (injectively & surjectively) in the
same range, we find many famous permutations related to binary expansion of
n, e.g. the (binary) Gray code A003188 and its inverse A006068, their
lesser known cousin Blue code A193231, bijective version of base-2 digit
reverse A057889, and at least scores (hundreds?) of others.

Similarly by selecting some other set of subranges, from whose confines the
cycles of the permutation are not allowed to "leak out" (e.g. n! ...
(n+1)!-1 or F(n) ... F(n+1)-1 where F is your favorite monotonic N -> N
function that starts with letter "F") . But of course most of these are all
simple base-related sequences. Another criteria might be that the numbers
in the cycle should all have the same prime-signature. Still, all the
permutations in this general scheme must have finite cycles. So this might
be one top-level criterion: has (or seems to have) infinite cycles, or has
been proved (including obvious/"by definition" cases) to contain only
finite cycles.


Best regards,

Antti




On Wed, Apr 11, 2018 at 8:19 PM, Antti Karttunen <antti.karttunen at gmail.com>
wrote:

>
> Neil Sloane wrote in
> http://list.seqfan.eu/pipermail/seqfan/2018-April/018575.html
> in response to a question by Michel Marcus ( http://list.seqfan.eu/
> pipermail/seqfan/2018-April/018573.html )
>
> > well of course ideally the best way is to use the Index entry
>
> > permutations of the positive (or nonnegative) integers , sequences related
> to :
>
> > but that is probably not up to date
>
> > To make it more up-to-date, we need to add more A-numbers to
> > that Index, and we need to add more
> > links to the Index from those A-numbers. Here is the link to add:
>
> > <a href="/index/Per#IntegerPermutation">Index entries for sequences that
> are permutations of the natural numbers</a>
>
> > which I took from the classic permutation A006368.
>
> My comment:
>
> I think we need to create many subcategories under that category. I myself
> have submitted (or infested, if you wish :-) OEIS with almost a thousand
> permutations of natural numbers, and countless other people with many more.
> Just listing those A-numbers, without even a possiblity to see their names
> with mouse-hover-over wouldn't actually help at all compared to just
> searching with
> https://oeis.org/search?q=link%3Aintegerpermutation&
> sort=&language=&go=Search
> (this gives 1766 entries, but I am sure there are many that have not
> included the category-link).
>
> So we would need to add some thought how to make a useful classification
> of subcategories here (of course those subcategories do not need to be
> mutually exclusive!).
>
> E.g., I am myself fond of permutations that are usually simple mappings
> based on various underlying combinatorial structures present either in the
> prime (or other) factorization of n, or in some simple base-expansion
> (base-2, Zeckendorf, etc). An example:
> https://oeis.org/A273671
> which involves Stern-Brocot tree and the exponents in prime factorization
> of n interpreted in balanced binary expansion.
> or https://oeis.org/A227351 which involves mapping between base-2 and
> Fibonacci-representations of n.
>
>
> On the other hand, many people prefer permutations based on some greedy
> criteria, where a(n) is the least number such that it satisfies certain
> criteria in respect to all the previous, or immediately previous,
> especially if it is not (or was not) immediately obvious whether the
> sequence actually is surjective and thus a permutation. (EKG-sequence, for
> example, https://oeis.org/A064413 )
>
> So, permutations involving greedy algorithm (and I think this could be
> subdivided further), permutations involving prime factorization of n,
> permutations based on base-2, -3, Fibonacci, Factorial, -10 expansion of n,
> and so on? Any ideas?
>
>
>
> Best regards,
>
> Antti
>
>
>
>
>
>