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.

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

Author

Olivier Gérard, Jun 20 2021

Keywords

• nonn
• tabl

Comments

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

Examples

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

References

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

Links

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

Crossrefs

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.

Programs

Maple

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

Mathematica

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

Formula

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)