[seqfan] Re: Interesting(?) sequence from permutations

[Neil Sloane]

as always, the answer is that if a sequence is interesting enough
to be discussed on this mailing list (and this one certainly is) then it
should be added to the OEIS! Neil

On Fri, Jun 22, 2012 at 10:52 PM, David Wilson <davidwwilson at comcast.net>wrote:

> For n >= 0, list the permutations of {0..n} in reverse lexical order:
>
> n = 0:
>
> 0
>
> n = 1:
>
> 1,0
> 0,1
>
> n = 2:
>
> 2,1,0
> 2,0,1
> 1,2,0
> 1,0,2
> 0,2,1
> 0,1,2
>
> n = 3:
>
> 3,2,1,0
> 3,2,0,1
> 3,1,2,0
> 3,1,0,2
> 3,0,2,1
> 3,0,1,2
> 2,3,1,0
> 2,3,0,1
> 2,1,3,0
> 2,1,0,3
> 2,0,3,1
> 2,0,1,3
> 1,3,2,0
> 1,3,0,2
> 1,2,3,0
> 1,2,0,3
> 1,0,3,2
> 1,0,2,3
> 0,3,2,1
> 0,3,1,2
> 0,2,3,1
> 0,2,1,3
> 0,1,3,2
> 0,1,2,3
>
> Note that
>
> The last column of the list for n = 0 is a proper prefix of the last
> column of the list for n = 1.
> The last column of the list for n = 1 is a proper prefix of the last
> column of the list for n = 2.
> The last column of the list for n = 2 is a proper prefix of the last
> column of the list for n = 3.
>
> In general, the last column of the list for n is a prefix of the last
> column for n+1 (easy enough to prove).
>
> By increasing n, we can extend the last column indefinitely to obtain an
> infinite sequence (indexed starting at 0):
>
> 0,1,0,2,1,2,0,1,0,3,1,3,0,2,0,**3,2,3,1,2,1,3,2,3,...
>
> I cannot find this sequence or a simple variant in the OEIS, but perhaps I
> did not looking hard enough.
>
> At any rate, this sequence has some interesting properties:
>
> - Elements alternately increase and decrease.
> - a(A007489(n)) = n is the first occurrence of n in the sequence.
> - If m > n, the number of m's in any prefix of the sequence cannot exceed
> the number of n's in that prefix.
> - For 0 <= m < n, there are (n-1)! m's among the first n! elements.
> - a(k) + a(n!-1-k) = n-1.
>
> The following C++ function computes a(n) very efficiently:
>
> int a(int n)
> {
>    int k = 0;
>    for (int m = 2; n > 0; m++)
>    {
>        if (k >= m - 1 - n%m)
>            k++;
>        n /= m;
>    }
>    return k;
> }
>
>
>
>
>
> ______________________________**_________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>



-- 
Dear Friends, I have now retired from AT&T. New coordinates:

Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com