A345461 - OEIS

%I #24 Aug 11 2021 09:17:52

%S 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,

%T 7,1,1,40320,12984,3383,732,108,7,1,1,362880,117513,31572,7043,1292,

%U 167,9,1,1,3628800,1182540,324112,75350,14522,2384,260,11,1,1

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

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

%C The length of each row is n.

%C 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.

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

%e Triangle begins:

%e .

%e      1;

%e      2,     1;

%e      6,     1,    1;

%e     24,     6,    1,   1;

%e    120,    38,    7,   1,  1;

%e    720,   232,   53,   7,  1,  1;

%e   5040,  1607,  404,  74,  7,  1,  1;

%e .

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

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

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

%Y Cf. A345464 (first column).

%K tabl,nonn

%O 1,2

%A _Olivier Gérard_, Jun 20 2021