login
A345453
Triangle of optimist numbers T(n,k) (n >= 1, 0 <= k <= n-1) read by rows: permutations needing k steps to be sorted by the "optimist" algorithm.
2
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, 1, 769, 11340, 19868, 7564, 764, 14, 0, 1, 1793, 50248, 162836, 119586, 26531, 1855, 30, 0, 1, 4097, 209900, 1179520, 1514171, 621622, 94192, 5223, 74, 0
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
Cf. A008292 (Eulerian numbers).
Cf. A000337 (second column (k=1))
Sequence in context: A221800 A291774 A222061 * A064315 A371994 A227322
KEYWORD
nonn,tabl
AUTHOR
Olivier Gérard, Jun 20 2021
STATUS
approved