A279683 - OEIS

%I #35 Jan 19 2022 12:10:15

%S 0,0,1,9,78,750,8220,102900,1463280,23451120,419942880,8331634080,

%T 181689298560,4323472433280,111534141438720,3101254066310400,

%U 92468631077222400,2943141763622860800,99596858633182310400,3570677764371119001600,135190500045467682816000

%N Number of move operations required to sort all permutations of [n] by MTF sort.

%C 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.

%C Conjecture: primes p such that p^4 divides a(p) are the Wolstenholme primes A088164. - _Amiram Eldar_ and _Thomas Ordowski_, Jan 15 2020

%H Alois P. Heinz, <a href="/A279683/b279683.txt">Table of n, a(n) for n = 0..404</a>

%H Project Euler, <a href="https://projecteuler.net/problem=523">Problem 523: First Sort I</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Sorting_algorithm">Sorting algorithm</a>

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>

%F a(n) = a(n-1)*n + (n-1)! * (2^(n-1)-1) for n>0, a(0) = 0.

%F a(n) = (4*n-3)*a(n-1)-(n-1)*(5*n-7)*a(n-2)+(2*n-2)*(n-2)^2*a(n-3) for n>2.

%F a(n) ~ 2^n * (n-1)!. - _Vaclav Kotesovec_, Dec 25 2016

%F a(n) = n! * Sum_{k=1..n} (2^(k-1)-1)/k = A000142(n)*A330718(n)/A330719(n), for n > 0. - _Amiram Eldar_ and _Thomas Ordowski_, Jan 15 2020

%e a(0) = a(1) = 0 because 0 or 1 elements are already sorted.

%e a(2) = 1: [1,2] is sorted and [2,1] needs one move.

%e a(3) = 9: [1,2,3](0), [1,3,2]->[2,1,3]->[1,2,3](2), [2,1,3]->[1,2,3](1), [2,3,1]->[1,2,3](1), [3,1,2]->[1,3,2]->[2,1,3]->[1,2,3](3), [3,2,1]->[2,3,1]->[1,2,3](2); sum of all moves gives 0+2+1+1+3+2 = 9.

%p a:= proc(n) option remember;

%p       `if`(n=0, 0, a(n-1)*n + (n-1)! * (2^(n-1)-1))

%p     end:

%p seq(a(n), n=0..20);

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<3, [0$2, 1][n+1],

%p       (4*n-3)*a(n-1)-(n-1)*(5*n-7)*a(n-2)+(2*n-2)*(n-2)^2*a(n-3))

%p     end:

%p seq(a(n), n=0..20);

%t a[0] = 0; a[n_] := a[n] = a[n-1]*n + (n-1)!*(2^(n-1) - 1);

%t Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, May 30 2018 *)

%Y Cf. A000142, A212395, A240797, A280970, A330718, A330719.

%K nonn

%O 0,4

%A _Alois P. Heinz_, Dec 16 2016