sequences that are permutations

[Antti Karttunen]

"N. J. A. Sloane" wrote:

> Howard Landman <howard at polyamory.org> has put together a preliminary
> list of the sequences that are permutations of the natural numbers
> (or in some cases of the nonnegative integers).
>
> Here is the current version.  If anyone knows of other examples,
> please send them to me (njas).

I think most of these could be found with a simple program, that checks
that A) the sequence does not contain duplicates,
B) all integers in range [1,n] occur for some small n (say 20). And then
one has to check manually what one gets. (There might be interesting
conjectures lurking there...)
This would leave out only "wildly fluctuating" permutations like this one:

ID Number: A011262
Sequence:  1,4,9,2,25,36,49,16,3,100,121,18,169,196,225,8,289,12,361,
           50,441,484,529,144,5,676,81,98,841,900,961,64,1089,1156,
           1225,6,1369,1444,1521,400,1681,1764,1849,242,75,2116,2209,
           72,7,20,2601,338,2809,324,3025,784,3249
Name:      In the prime factorization of n, increment odd powers and decrement
              even powers (multiplicative and self-inverse).
Formula:   Multiplicative with f(p^k) = p^(k-1) if k even, p^(k+1) if k odd.
See also:  Cf. A011264.
Keywords:  nonn,easy
Offset:    1
Author(s): Marc Le Brun (mlb at well.com)

and: (but this one is already in the index:)
ID Number: A059884
Sequence:  0,1,2,4,8,3,128,5,32,9,32768,6,2147483648,129,10,16,
           9223372036854775808,33,
           170141183460469231731687303715884105728,12,130,32769
Name:      Prime factorization of n encoded by recursively interleaving bits of
              successive prime exponents.


Also, all the "permutations of the natural numbers" that I have
submitted (and some other SeqFanatiques too) can be found with keywords
"permutations of the natural numbers", although most of those are not yet in the
Index entry itself.

Ah, here are some vague thoughts that I wrote about these kind of sequences
in March 2000. Comments are welcome.



Some possible methods to create permutations of the natural numbers:

1) From any infinite sequence Axxxxxx construct a permutation of natural
   numbers, by reversing each consecutive block of abs(Axxxxxx[n])
   integers. If Axxxxxx does not contain any term > 1, then
   the result is natural numbers A000027 itself.
   The resulting permutation is always self-inverse
   (consists of fixed terms and/or transpositions only).
   Dumb as sequences, but might have some uses
   as functions.

2) From any infinite sequence Axxxxxx whose terms are all discrete
   and positive, and whose complement Ayyyyyy is likewise infinite
   (thus A000027 won't do), construct a self-inverse permutation
   composed of discrete transpositions, by swapping each
   Axxxxxx[n] <-> Ayyyyyy[n].
   I.e. From 3,6,9,12,15,18,21,...
        and  1,2,4,5,7,8,10,11
     we get  3,6,1,9,12,2,15,18,4,...
   E.g. A003622[n] <-> A022342[n].
   Most of these are quite dumb as well.

3a) From any infinite sequence known to contain all natural numbers,
   but some of them more than once, construct a permutation
   by pruning off all duplicates after the first
   occurrence of each value n. (E.g. from Pascal 2-1 triangle A029654).


3b) Like above, but prune off all duplicates before the _last_
   proved occurrence of each value n. Here the last occurrence
   should of course be well-defined.


3c) Like 3a and 3b, but leave the f(n):th occurrence of each value of n,
    where f is some arbitrary, but well-defined function.


4) From any function f(x) proved to have any particular integral value y
   with only finite number of integer arguments x1,x2,...,xn
   (e.g. number theoretic functions phi and sigma), construct
   a permutation of natural numbers by first listing (in some definite
   order) all x for which f(x) = y1 (the global minimum for f),
   then all x for which f(x) = y2 (the nearest possible value
   greater than y1), then all x for which f(x) = y3, etc.
   Note that y1,y2,y3 are not necessarily consecutive.
   Example: invphi sequence. A032447


5) From any two distinct infinite sequences A and B which have been proved
   to span exactly the same set of distinct numbers or other objects,
   construct a permutation of natural numbers by indexing A with B,
   and its inverse by indexing B with A.

   Here the set of distinct numbers can for example be

   * all non-negative integers (A001477 itself and A003188, i.e. Gray Code).
         (binary encoding of square-frees A048672, Bower's A052330, etc.)
         (If we look the binary representation of n, then the actual set of
         distinct objects that are spanned here is the set of subsets
         of the cardinality Aleph-0 set.)

   * all binary sequences with some combinatorial condition,
     e.g. Fibbinary numbers (no ...11..), numbers composed of
     exactly n or max. n bits in their binary expansion, etc.

   * all sets of sequences of digits [{0,1},{0-2},{0-3},...,{0-n}]
     (one such set is factorial number representation of non-negative
      integers, but are there any others, which would result
      a different ordering naturally?)

   * all rational fractions. (e.g. A054424)

   * all C with algebraic (non-transcedental) R and I components,
      or some subset?
      E.g. is there a way to "canonically" list all quadratic polynomials
      with integral coefficients to get a "canonical" list
      of quadratic roots in C (or just the Real ones), and then the
      other sequence would be constructed from "canonical list"
      of infinite, but periodic continued fractions.


6) From any known two permutations of natural numbers (not necessarily
   distinct), construct possibly one or two new ones by composing
   them with each other, from the right and from the left.
   (I.e. this is not-necessarily commutative multiplication of permutations.)


7) Walk through infinite square lattice, starting from the corner, in some
    way (e.g. some regular knight walk), and then read the sequence
    from the successive antidiagonals of this triangular table.
    (Simple variants of this theme: A038722, A056537, A060736)


But in more fundamental way, maybe one good classification could be
according to a cycle structure of the permutation:

A) cycles are finite and bounded to regular "regions". (e.g. the Gray code A003188,
where the regions are contained between each subsequence 2^n - 2^(n+1).
B) cycles are finite, but less clearly bounded, but some upper and lower bounds
can still be found.

(in above two cases one could count the number of cycles ("equivalence classes")
formed in each "region", even although they might not have any
clear combinatorial significance at all...)

C) cycles can be known to be finite, but with no known structure.
D) one or more of the cycles are infinite.

E.g. from permutations like:
ID Number: A057114
Sequence:  3,1,7,2,6,14,15,4,5,12,13,28,29,30,31,8,9,10,11,24,25,26,27,
           56,57,58,59,60,61,62,63,16,17,18,19,20,21,22,23,48,49,50,51,
           52,53,54,55,112,113,114,115,116,117,118,119,120,121,122,123,
           124,125,126,127,32,33,34,35,36,37,38,39,40,41,42,43,44,45,
           46,47,96,97,98,99,100,101,102,103
Name:      Order-preserving permutation of the rational numbers (x -> x+1);
              positions in Stern-Brocot tree.
we know that only cycle lengths that can occur are 1 (but not in this one)
and infinite.

and permutations like this one (an inspiration for famous 3x+1 problem?, not
in index! Is this a permutation conjecturally only?):

ID Number: A006369 (Formerly M2245)
Sequence:  0,1,3,2,5,7,4,9,11,6,13,15,8,17,19,10,21,23,12,25,27,14,29,
           31,16,33,35,18,37,39,20,41,43,22,45,47,24,49,51,26,53,55,28,
           57,59,30,61,63,32,65,67,34,69,71,36,73,75,38
Name:      Nearest integer to 4n/3 unless that is an integer, when 2n/3.


BTW, here's are an interesting paper regarding the topic:
http://www.cecm.sfu.ca/organics/papers/buhler/index.html



That's all for now, maybe some day I have enough time to actually
do this in more thorough fashion...


Terveisin,

Antti Karttunen



>
>
> The entries in the index will also be updated.
>
> Sequence-Inverse
> A000027 - self-inverse
> A002251 - self-inverse
> A003100 - self-inverse
> A003188 - A006068
> A004484 - A064206
> A004485 - A064207
> A004486 - A064208
> A004487 - A064211
> A019444 - self-inverse
> A026243 - self-inverse
> A029654 - A064360
> A064413 - A064664
> A032447 - A064275
> A035312 - A035358
> A035506 - A064357
> A035513 - A064274
> A047708 - A048850
> A048647 - A064212
> A048672 - A064273
> A048673 - A064216
> A048679 - A048680
> A052330 - A064358
> A059900 - A059884
> A052331 - A064359
> A054238 - A054239
> A054424 - A054426
> A054427 - A054428
> A054429 - self-inverse
> A054430 - self-inverse
> A054081 - n/a           array: rows are permutations but it isn't itself
>
> I think the squares of these permutations also should be in the database.
> I suggested this to Howard, but this is a big job and if anyone else would
> be willing to send in some "squares" that would be very helpful.
>
> If f is one of the permutations mentioned above
> then what I mean is the sequence
> f(f(1)), f(f(2)), f(f(3)), f(f(4)), ...
> - except perhaps beginning with f(f(0)) if that is appropriate.
>
> Of course many of these may already be in the database; if so this should be noted.
>
> Neil Sloane