|
|
A280970
|
|
Number of comparisons required to sort all permutations of [n] by MTF sort.
|
|
2
|
|
|
0, 0, 3, 25, 208, 1928, 20328, 244536, 3347328, 51858432, 902874240, 17523066240, 375931514880, 8842225904640, 226294152053760, 6258916573056000, 185978410684416000, 5906514709831680000, 199606607730561024000, 7150186413112651776000, 270578540735613960192000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
MTF sort is an (inefficient) sorting algorithm: the first element that is smaller than its predecessor is moved to front repeatedly until the sequence is sorted. Comparisons of adjacent elements always begin at the front and are continued until the last or the next element to be moved is found.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = a(n-1)*n + (n-1)! * (2^n+(n-3)*n/2) for n>1, a(0) = a(1) = 0.
|
|
MAPLE
|
a:= proc(n) option remember;
`if`(n<2, 0, a(n-1)*n + (n-1)! * (2^n+(n-3)*n/2))
end:
seq(a(n), n=0..20);
# second Maple program:
a:= proc(n) option remember;
`if`(n<7, [0$2, 3, 25, 208, 1928, 20328][n+1],
((4*n^2-23*n+2)*a(n-1)-(5*n^3-28*n^2-n+54)*a(n-2)
+(2*n-4)*(n^3-2*n^2-24*n+52)*a(n-3)
-(4*n-8)*(n-4)*(n-3)^2*a(n-4))/(n-6))
end:
seq(a(n), n=0..20);
|
|
MATHEMATICA
|
Flatten[{0, Simplify[Table[n!*(n*(n-5)/4 - Pi*I - 1 - 2^(1+n)*LerchPhi[2, 1, 1+n]) , {n, 1, 20}]]}] (* Vaclav Kotesovec, Jan 12 2017 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|