[seqfan] Sequences for Orderings

[Marc LeBrun]

The OEIS contains many sequences which are "permutations of the integers".

Naturally each such permutation a(n) presents an "ordering of the integers"
determined by what values appear earlier in the sequence.

Let's write the ordering relation as [<] ("bracket-less-than"), defined by

  a(j) [<] a(k)  just when  j < k

(and of course similarly for [<=], [>], [>=], [min], [max] and so on).

An example permutation sequence is A065190: 1, 3, 2, 5, 4, 7, 6, 9, 8,...
wherein the implied ordering relation gives, for instance, that 3 [<] 2
because 3 appears before 2.

However, as discussed here previously, there are many interesting orderings
of the integers which are NOT permutations, a favorite example being the
Sharkovsky ordering, http://mathworld.wolfram.com/SharkovskysTheorem.html

Alas it can't ever be directly entered in the OEIS, the way a permutation
can, even in principle, because no matter how large a B-file we gave it it
would be indistinguishable from just the sequence of odd numbers >= 3.

One way to address this would be a table where T(j,k) encodes when j [<] k.

However I'd like to instead propose that a nicer way to represent an
arbitrary ordering relation [<] is as a sequence where a(n) gives the index
of n when [1, 2, 3,... n] is sorted with respect to [<].

First, all permutation sequences can be encoded this way.  For example
A065190 is represented as 1, 2, 2, 4, 4, 6, 6,... = A131005

Moreover this works for any ordering.  For example to represent the trivial
ordering "all odds < all evens" we get (an offset of) the badly named "An
obvious mixture of two sequences" A029578 = 1, 2, 2, 4, 3, 6, 4, 8, 5, 10...

In this scheme every ordering is represented by what I call a "gradual"
sequence, where 1 <= a(n) <= n, and every such sequence corresponds 1-to-1
to an ordering (eg the "all 1's" sequence A000012 represents the integers in
"reverse order", that is, sorted by [<] := >!)

Questions/suggestions/projects for Seqfans:

  *  Is this a good "canonical" scheme for entering orderings in the OEIS?

  *  Is there an accepted name for the "index sequence" representing an
ordering?  For the "gradual" property?

  *  Anybody want to submit the Sharkovsky ordering?  Others?

  *  How about annotating all those "permutation" sequences with links to
their index sequences, and vice versa?  And perhaps even submitting the
missing partners for any really significant sequences?

Thanks!
  --MLB