A345461 Triangle T(n,k) (n >= 1, 0 <= k <= n-1) read by rows: number of distinct permutations after k steps of the "optimist" algorithm.

1, 2, 1, 6, 1, 1, 24, 6, 1, 1, 120, 38, 7, 1, 1, 720, 232, 53, 7, 1, 1, 5040, 1607, 404, 74, 7, 1, 1, 40320, 12984, 3383, 732, 108, 7, 1, 1, 362880, 117513, 31572, 7043, 1292, 167, 9, 1, 1, 3628800, 1182540, 324112, 75350, 14522, 2384, 260, 11, 1, 1

Offset: 1

Author

Olivier Gérard, Jun 20 2021

Keywords

• tabl
• nonn

Comments

Start with the n! permutations of order n. Apply an iteration of the "optimist" sorting algorithm. Count the distinct permutations, until all are sorted.

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. An example is given in A345453.

Examples

			Triangle begins:
.
     1;
     2,     1;
     6,     1,    1;
    24,     6,    1,   1;
   120,    38,    7,   1,  1;
   720,   232,   53,   7,  1,  1;
  5040,  1607,  404,  74,  7,  1,  1;
.
		

Crossrefs

Cf. A345453 (permutations according to number of steps for sorting).

Cf. A321352 and A008305 (the equivalent for Eulerian numbers).

Cf. A345462 (the equivalent for Stirling numbers of 1st kind).

Cf. A345464 (first column).

Formula

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