[seqfan] Interesting(?) sequence from permutations

[David Wilson]

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