38.2 The position of a permutation in the universal sequence 1007
38.2 The position of a permutation in the universal sequence
quence
Given a permutationLn, we want to determine its position in the enu-
meration scheme above. Forj=n,n− 1 , ..., 2 , let
(i)rjbe the number of elements inLjon the right hand side ofj,
(ii)Lj− 1 be the sequenceLjwithjdeleted.
Then, the position number of the permutationLnis
1+r 2 ×1! +r 3 ×2! +···+rn×(n−1)!.This number can be computed recursively as follows.
sn=rn,
sn− 1 =sn×(n−1) +rk− 1 ,
..
.
sj− 1 =sj×(j−1) +rj− 1 ,
..
.
s 2 =s 2 ×2+r 2 ,
s 1 =s 2 ×1+1.Example
Consider the permutationL=(1, 4 , 6 , 2 , 3 , 7 , 9 , 8 ,5).
jLj rj sj
9(1, 4 , 6 , 2 , 3 , 7 , 9 , 8 ,5) 2 2
8(1, 4 , 6 , 2 , 3 , 7 , 8 ,5) 1 17
7(1, 4 , 6 , 2 , 3 , 7 ,5) 1 120
6(1, 4 , 6 , 2 , 3 ,5) 3 723
5(1, 4 , 2 , 3 ,5) 0 3615
4(1, 4 , 2 ,3) 2 14462
3(1, 2 ,3) 0 43386
2(1,2) 0 86772
1 (1) 1 86773
This permutation appears as the 86773-th in the universal sequence.