OFFSET
1,5
COMMENTS
This is a decomposition of the permutations of order n.
The length of each row is n.
The optimist algorithm is: rotate right all currently unsorted letters by the distance between the first unsorted one and its sorted position.
Conjecture: each row is unimodal.
FORMULA
T(n,1) = 1; T(n,n-1)=0 for n>2;
T(n,2) = (n - 2)*2^(n - 1) + 1
EXAMPLE
Permutation {2,1,3,7,6,5,4} needs 3 steps to reach the identity:
0: {2,1,3,7,6,5,4}: rotate (2,1,7,6,5,4) 1 step right
1: {4,2,3,1,7,6,5}: rotate (4,1,7,5) 1 step right
2: {5,2,3,4,1,6,7}: rotate (5,1) 1 step right
3: {1,2,3,4,5,6,7}: identity. End.
Triangle begins:
1;
1, 1;
1, 5, 0;
1, 17, 6, 0;
1, 49, 64, 6, 0;
1, 129, 432, 150, 8, 0;
1, 321, 2356, 2016, 336, 10, 0;
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Olivier Gérard, Jun 20 2021
STATUS
approved