A321352 -id:A321352 - cp's OEIS frontend

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

Olivier Gérard, Jun 20 2021

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.

			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;
.

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

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

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

Original entry on oeis.org

1, 2, 1, 6, 3, 1, 24, 13, 4, 1, 120, 67, 23, 5, 1, 720, 411, 146, 36, 6, 1, 5040, 2921, 1067, 272, 52, 7, 1, 40320, 23633, 8800, 2311, 456, 71, 8, 1, 362880, 214551, 81055, 21723, 4419, 709, 93, 9, 1, 3628800, 2160343, 825382, 224650, 46654, 7720, 1042, 118, 10, 1

Offset: 1

Olivier Gérard, Jun 20 2021

The first transposition algorithm is: if the permutation is sorted, then exit; otherwise, exchange the first unsorted letter with the letter currently at its index. Repeat.
At each step at least 1 letter (possibly 2) is sorted.
If one counts the steps necessary to reach the identity, this gives the Stirling numbers of the first kind (reversed).

			Triangle begins:
      1;
      2,     1;
      6,     3,    1;
     24,    13,    4,    1;
    120,    67,   23,    5,   1;
    720,   411,  146,   36,   6,  1;
   5040,  2921, 1067,  272,  52,  7, 1;
  40320, 23633, 8800, 2311, 456, 71, 8, 1;
  ...

D. E. Knuth, The Art of Computer Programming, Vol. 3 / Sorting and Searching, Addison-Wesley, 1973.

Alois P. Heinz, Rows n = 1..150, flattened

Cf. A321352, A345461 (same idea for other sorting algorithms).
Cf. A180191 (second column, k=1).
Cf. A107111 a triangle with some common parts.
Cf. A143689 (diagonal T(n,n-3)).
Cf. A000142, A000166, A000255, A000274, A000313, A010027, A123513.

b:= proc(n, k) option remember; (k+1)!*
      binomial(n, k)*add((-1)^i/i!, i=0..k+1)/n
    end:
T:= proc(n, k) option remember;
     `if`(k=0, n!, T(n, k-1)-b(n, n-k+1))
    end:
seq(seq(T(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Aug 11 2021

b[n_, k_] := b[n, k] = (k+1)!*Binomial[n, k]*Sum[(-1)^i/i!, {i, 0, k+1}]/n;
T[n_, k_] := T[n, k] = If[k == 0, n!, T[n, k-1] - b[n, n-k+1]];
Table[Table[T[n, k], {k, 0, n - 1}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 06 2022, after Alois P. Heinz *)

T(n,0) = n!; T(n,n-3) = (3*(n-1)^2 - n + 3)/2.
From Alois P. Heinz, Aug 11 2021: (Start)
T(n,k) = T(n,k-1) - A010027(n,n-k) for k >= 1.
T(n,k) - T(n,k+1) = A123513(n,k).
T(n,0) - T(n,1) = A000255(n-1) for n >= 2.
T(n,1) - T(n,2) = A000166(n) for n >= 3.
T(n,2) - T(n,3) = A000274(n) for n >= 4.
T(n,3) - T(n,4) = A000313(n) for n >= 5. (End)

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula