OFFSET
0,3
COMMENTS
a(n) is the position of the zero in the inverse permutation of the one generated by "Algorithm E" given in D. E. Knuth, TAOCP, Section 7.2.1.2.
Alternatively, the first element in the permutation (see example).
Starting with the identical permutation, the list of permutations in star-transposition order can be generated by swapping p(a(n)) with p(a(n+1)). - Joerg Arndt, Dec 25 2023
REFERENCES
D. E. Knuth, TAOCP, Section 7.2.1.2.
LINKS
Joerg Arndt, Table of n, a(n) for n = 0..5039
Joerg Arndt, Matters Computational (The Fxtbook), section 10.8 "Star-transposition order", pp.257-258
FORMULA
a(k!) = k (for k>=1) and a(j) < k for j<k!. [Joerg Arndt, Mar 20 2014]
EXAMPLE
permutation swap inverse permutation
0: [ 0 1 2 3 ] [ 0 1 2 3 ]
1: [ 1 0 2 3 ] (0, 1) [ 1 0 2 3 ]
2: [ 2 0 1 3 ] (0, 2) [ 1 2 0 3 ]
3: [ 0 2 1 3 ] (0, 1) [ 0 2 1 3 ]
4: [ 1 2 0 3 ] (0, 2) [ 2 0 1 3 ]
5: [ 2 1 0 3 ] (0, 1) [ 2 1 0 3 ]
6: [ 3 1 0 2 ] (0, 3) [ 2 1 3 0 ]
7: [ 0 1 3 2 ] (0, 2) [ 0 1 3 2 ]
8: [ 1 0 3 2 ] (0, 1) [ 1 0 3 2 ]
9: [ 3 0 1 2 ] (0, 2) [ 1 2 3 0 ]
10: [ 0 3 1 2 ] (0, 1) [ 0 2 3 1 ]
11: [ 1 3 0 2 ] (0, 2) [ 2 0 3 1 ]
12: [ 2 3 0 1 ] (0, 3) [ 2 3 0 1 ]
13: [ 3 2 0 1 ] (0, 1) [ 2 3 1 0 ]
14: [ 0 2 3 1 ] (0, 2) [ 0 3 1 2 ]
15: [ 2 0 3 1 ] (0, 1) [ 1 3 0 2 ]
16: [ 3 0 2 1 ] (0, 2) [ 1 3 2 0 ]
17: [ 0 3 2 1 ] (0, 1) [ 0 3 2 1 ]
18: [ 1 3 2 0 ] (0, 3) [ 3 0 2 1 ]
19: [ 2 3 1 0 ] (0, 2) [ 3 2 0 1 ]
20: [ 3 2 1 0 ] (0, 1) [ 3 2 1 0 ]
21: [ 1 2 3 0 ] (0, 2) [ 3 0 1 2 ]
22: [ 2 1 3 0 ] (0, 1) [ 3 1 0 2 ]
23: [ 3 1 2 0 ] (0, 2) [ 3 1 2 0 ]
PROG
(PARI)
ss( n ) =
{
my(k, f, nf, v);
f = 1; k = 2; /* f==(k-1)! */
nf = f * k; /* nf==k! */
v = vector(n);
for ( p=1, #v-1,
if ( p>=nf, f=nf; k+=1; nf*=k );
v[p+1] = (v[p-f+1]-1) % k;
);
return(v);
}
ss( 5! )
(PARI) \\ individual terms:
a( n ) =
{
my( ret = 0, k = 0 );
while ( n != 0 ,
k += 1;
my( d = n % (k+1) );
n \= (k+1);
ret = (ret - d) % (k+1);
);
return( ret );
}
vector(5!, n, a(n-1) ) \\ Joerg Arndt, Dec 28 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
Joerg Arndt, Apr 25 2009
STATUS
approved