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