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.

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

Author

Olivier Gérard, Jun 20 2021

Keywords

• nonn
• tabl

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.

Examples

			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))

Formula

T(n,1) = 1; T(n,n-1)=0 for n>2;

T(n,2) = (n - 2)*2^(n - 1) + 1