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