OFFSET
1,2
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).
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
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)
EXAMPLE
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;
...
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 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Olivier Gérard, Jun 20 2021
STATUS
approved