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
Alois P. Heinz, Table of n, a(n) for n = 0..404
Project Euler, Problem 523: First Sort I
Wikipedia, Sorting algorithm
FORMULA
a(n) = a(n-1)*n + (n-1)! * (2^n+(n-3)*n/2) for n>1, a(0) = a(1) = 0.
a(n) ~ (n-1)! * 2^(n+1). - Vaclav Kotesovec, Jan 12 2017
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
Alois P. Heinz, Jan 11 2017
STATUS
approved