cp's OEIS Frontend

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.

%I A345462 #35 Mar 06 2022 04:44:06
%S A345462 1,2,1,6,3,1,24,13,4,1,120,67,23,5,1,720,411,146,36,6,1,5040,2921,
%T A345462 1067,272,52,7,1,40320,23633,8800,2311,456,71,8,1,362880,214551,81055,
%U A345462 21723,4419,709,93,9,1,3628800,2160343,825382,224650,46654,7720,1042,118,10,1
%N 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.
%C A345462 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.
%C A345462 At each step at least 1 letter (possibly 2) is sorted.
%C A345462 If one counts the steps necessary to reach the identity, this gives the Stirling numbers of the first kind (reversed).
%D A345462 D. E. Knuth, The Art of Computer Programming, Vol. 3 / Sorting and Searching, Addison-Wesley, 1973.
%H A345462 Alois P. Heinz, <a href="/A345462/b345462.txt">Rows n = 1..150, flattened</a>
%F A345462 T(n,0) = n!; T(n,n-3) = (3*(n-1)^2 - n + 3)/2.
%F A345462 From _Alois P. Heinz_, Aug 11 2021: (Start)
%F A345462 T(n,k) = T(n,k-1) - A010027(n,n-k) for k >= 1.
%F A345462 T(n,k) - T(n,k+1) = A123513(n,k).
%F A345462 T(n,0) - T(n,1) = A000255(n-1) for n >= 2.
%F A345462 T(n,1) - T(n,2) = A000166(n) for n >= 3.
%F A345462 T(n,2) - T(n,3) = A000274(n) for n >= 4.
%F A345462 T(n,3) - T(n,4) = A000313(n) for n >= 5. (End)
%e A345462 Triangle begins:
%e A345462       1;
%e A345462       2,     1;
%e A345462       6,     3,    1;
%e A345462      24,    13,    4,    1;
%e A345462     120,    67,   23,    5,   1;
%e A345462     720,   411,  146,   36,   6,  1;
%e A345462    5040,  2921, 1067,  272,  52,  7, 1;
%e A345462   40320, 23633, 8800, 2311, 456, 71, 8, 1;
%e A345462   ...
%p A345462 b:= proc(n, k) option remember; (k+1)!*
%p A345462       binomial(n, k)*add((-1)^i/i!, i=0..k+1)/n
%p A345462     end:
%p A345462 T:= proc(n, k) option remember;
%p A345462      `if`(k=0, n!, T(n, k-1)-b(n, n-k+1))
%p A345462     end:
%p A345462 seq(seq(T(n, k), k=0..n-1), n=1..10);  # _Alois P. Heinz_, Aug 11 2021
%t A345462 b[n_, k_] := b[n, k] = (k+1)!*Binomial[n, k]*Sum[(-1)^i/i!, {i, 0, k+1}]/n;
%t A345462 T[n_, k_] := T[n, k] = If[k == 0, n!, T[n, k-1] - b[n, n-k+1]];
%t A345462 Table[Table[T[n, k], {k, 0, n - 1}], {n, 1, 10}] // Flatten (* _Jean-François Alcover_, Mar 06 2022, after _Alois P. Heinz_ *)
%Y A345462 Cf. A321352, A345461 (same idea for other sorting algorithms).
%Y A345462 Cf. A180191 (second column, k=1).
%Y A345462 Cf. A107111 a triangle with some common parts.
%Y A345462 Cf. A143689 (diagonal T(n,n-3)).
%Y A345462 Cf. A000142, A000166, A000255, A000274, A000313, A010027, A123513.
%K A345462 nonn,tabl
%O A345462 1,2
%A A345462 _Olivier Gérard_, Jun 20 2021