# [seqfan] Re: Sequences for Orderings

franktaw at netscape.net franktaw at netscape.net
Fri Mar 26 23:29:32 CET 2010

```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.

-----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

*  Anybody want to submit the Sharkovsky ordering?  Others?