[seqfan] Interesting(?) sequence from permutations
David Wilson
davidwwilson at comcast.net
Sat Jun 23 04:52:27 CEST 2012
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;
}
More information about the SeqFan
mailing list