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

0, 0, 1, 9, 78, 750, 8220, 102900, 1463280, 23451120, 419942880, 8331634080, 181689298560, 4323472433280, 111534141438720, 3101254066310400, 92468631077222400, 2943141763622860800, 99596858633182310400, 3570677764371119001600, 135190500045467682816000

Offset

0,4

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.

Conjecture: primes p such that p^4 divides a(p) are the Wolstenholme primes A088164. - Amiram Eldar and Thomas Ordowski, Jan 15 2020

Links

Alois P. Heinz, Table of n, a(n) for n = 0..404

Project Euler, Problem 523: First Sort I

Wikipedia, Sorting algorithm

Index entries for sequences related to sorting

Formula

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

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.

a(n) ~ 2^n * (n-1)!. - Vaclav Kotesovec, Dec 25 2016

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

Example

a(0) = a(1) = 0 because 0 or 1 elements are already sorted.
a(2) = 1: [1,2] is sorted and [2,1] needs one move.
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.

Maple

a:= proc(n) option remember;
      `if`(n=0, 0, a(n-1)*n + (n-1)! * (2^(n-1)-1))
    end:
seq(a(n), n=0..20);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, [0$2, 1][n+1],
      (4*n-3)*a(n-1)-(n-1)*(5*n-7)*a(n-2)+(2*n-2)*(n-2)^2*a(n-3))
    end:
seq(a(n), n=0..20);

Mathematica

a[0] = 0; a[n_] := a[n] = a[n-1]*n + (n-1)!*(2^(n-1) - 1);
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 30 2018 *)

Crossrefs

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

Sequence in context: A254657 A231590 A240797 * A123918 A044577 A357281

Adjacent sequences: A279680 A279681 A279682 * A279684 A279685 A279686

Keyword

nonn

Author

Alois P. Heinz, Dec 16 2016

Status

approved