login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A279683 Number of move operations required to sort all permutations of [n] by MTF sort. 3
0, 0, 1, 9, 78, 750, 8220, 102900, 1463280, 23451120, 419942880, 8331634080, 181689298560, 4323472433280, 111534141438720, 3101254066310400, 92468631077222400, 2943141763622860800, 99596858633182310400, 3570677764371119001600, 135190500045467682816000 (list; graph; refs; listen; history; text; internal format)
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.

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

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. A212395, A240797, A280970.

Sequence in context: A254657 A231590 A240797 * A123918 A044577 A172203

Adjacent sequences:  A279680 A279681 A279682 * A279684 A279685 A279686

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Dec 16 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 17 22:17 EDT 2019. Contains 324200 sequences. (Running on oeis4.)