login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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+(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

Cf. A279683.

Sequence in context: A289164 A037783 A037587 * A222052 A230718 A112240

Adjacent sequences:  A280967 A280968 A280969 * A280971 A280972 A280973

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Jan 11 2017

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 February 25 21:28 EST 2021. Contains 341618 sequences. (Running on oeis4.)