|
|
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.
|
|
2
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
T(n,0) = n!; T(n,n-3) = (3*(n-1)^2 - n + 3)/2.
T(n,k) = T(n,k-1) - A010027(n,n-k) for k >= 1.
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:
|
|
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]];
|
|
CROSSREFS
|
Cf. A107111 a triangle with some common parts.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|