|
|
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.
|
|
2
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
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.
|
|
LINKS
|
|
|
FORMULA
|
T(n,0) = n!; T(n,n-1) = 1; T(n,n-2) = 1 for n > 2.
|
|
EXAMPLE
|
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. A345462 (the equivalent for Stirling numbers of 1st kind).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|