cp's OEIS Frontend

A280970 Number of comparisons required to sort all permutations of [n] by MTF sort.

%I A280970 #12 Jun 21 2017 18:53:25
%S A280970 0,0,3,25,208,1928,20328,244536,3347328,51858432,902874240,
%T A280970 17523066240,375931514880,8842225904640,226294152053760,
%U A280970 6258916573056000,185978410684416000,5906514709831680000,199606607730561024000,7150186413112651776000,270578540735613960192000
%N A280970 Number of comparisons required to sort all permutations of [n] by MTF sort.
%C A280970 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.
%H A280970 Alois P. Heinz, <a href="/A280970/b280970.txt">Table of n, a(n) for n = 0..404</a>
%H A280970 Project Euler, <a href="https://projecteuler.net/problem=523">Problem 523: First Sort I</a>
%H A280970 Wikipedia, <a href="https://en.wikipedia.org/wiki/Sorting_algorithm">Sorting algorithm</a>
%H A280970 <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%F A280970 a(n) = a(n-1)*n + (n-1)! * (2^n+(n-3)*n/2) for n>1, a(0) = a(1) = 0.
%F A280970 a(n) ~ (n-1)! * 2^(n+1). - _Vaclav Kotesovec_, Jan 12 2017
%p A280970 a:= proc(n) option remember;
%p A280970       `if`(n<2, 0, a(n-1)*n + (n-1)! * (2^n+(n-3)*n/2))
%p A280970     end:
%p A280970 seq(a(n), n=0..20);
%p A280970 # second Maple program:
%p A280970 a:= proc(n) option remember;
%p A280970      `if`(n<7, [0$2, 3, 25, 208, 1928, 20328][n+1],
%p A280970      ((4*n^2-23*n+2)*a(n-1)-(5*n^3-28*n^2-n+54)*a(n-2)
%p A280970       +(2*n-4)*(n^3-2*n^2-24*n+52)*a(n-3)
%p A280970       -(4*n-8)*(n-4)*(n-3)^2*a(n-4))/(n-6))
%p A280970     end:
%p A280970 seq(a(n), n=0..20);
%t A280970 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 *)
%Y A280970 Cf. A279683.
%K A280970 nonn
%O A280970 0,3
%A A280970 _Alois P. Heinz_, Jan 11 2017