[seqfan] Re: Sequences for Orderings

[franktaw at netscape.net]

Note that, for the reverse ordering, n [<] m iff n > m, the index 
sequence is the all ones sequence, A000012.

I believe that the index sequence for Sharkovsky's ordering starts 
1,1,1,2,2,3,3,5,4,6; this is not in the OEIS.

I think this is a good idea, but it needs to be documented; someone 
going to mathematical literature or on-line reference sources won't 
find it.  Basically, a quick description like that in Marc's note 
(quoted below) should either be included in a sequence (the index 
sequence for Sharkovsky's ordering seems like a good choice) or added 
to the OEIS as a separate document.  Whichever is done, this can then 
be referenced anywhere the idea is used.

-----
Just looking at finite sequences, there are a number of important 
sequences that can be enumerated by counting restrictions of this idea.

With no further restriction, we are counting the factorial numbers 
A000142.  If we require a(n+1) <= a(n) + 1, we get the Catalan numbers, 
A000108.  Requiring a(n+1) <= max(a(1),...,a(n)) + 1 gives us the Bell 
numbers A000110 (and this a standard representation for set 
partitions).  Restricting so that the number of occurrences of each m 
in a(1)..a(n) is at least the number of occurrences of m+1 in the same 
sequence gives us the involutions, A000085 (these are trivially in 
one-to-one correspondence with the Young tableaux).  Requiring a(n) <= 
a(n+1) <= a(n) + 1 gives us the count of compositions, A011782 
(essentially powers of 2).  Apply both of these last two restrictions 
and we are counting partitions, A000041.

Franklin T. Adams-Watters

-----Original Message-----
From: Marc LeBrun <mlb at well.com>

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