This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A212395 Number of move operations required to sort all permutations of [n] by insertion sort. 5
 0, 0, 3, 23, 164, 1252, 10512, 97344, 990432, 11010528, 132966720, 1734793920, 24330205440, 365150833920, 5840673108480, 99204809356800, 1783428104908800, 33833306484633600, 675513065777356800, 14160039606855475200, 310935875030323200000 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS a(n) is n! times the average number of move operations (A212396, A212397) required by an insertion sort of n (distinct) elements. LINKS Alois P. Heinz, Table of n, a(n) for n = 0..448 Wikipedia, Insertion sort FORMULA a(n) = a(n-1)*n + (n-1)! * (n-1)*(n+4)/2 for n>0, a(0) = 0. a(n) = n! * (n*(n+7)/4 - 2*H(n)) with n-th harmonic number H(n) = Sum_{k=1..n} 1/k = A001008(n)/A002805(n). a(n) = ((2*n^3+3*n^2-13*n+4)*a(n-1)-(n+4)*(n-1)^3*a(n-2))/((n-2)*(3+n)) for n>2. EXAMPLE a(0) = a(1) = 0 because 0 or 1 elements are already sorted. a(2) = 3: [1,2] is sorted and [2,1] needs 3 moves. a(3) = 23: [1,2,3]->(0), [1,3,2]->(3), [2,1,3]->(3), [2,3,1]->(4), [3,1,2]->(6), [3,2,1]->(7); sum of all moves gives 0+3+3+4+6+7 = 23. MAPLE a:= proc(n) option remember;       `if`(n=0, 0, a(n-1)*n + (n-1)! * (n-1)*(n+4)/2)     end: seq(a(n), n=0..30); # second Maple program: a:= proc(n) option remember; `if`(n<3, [0\$2, 3][n+1],       ((2*n^3+3*n^2-13*n+4)*a(n-1) -(n+4)*        (n-1)^3*a(n-2)) / ((n-2)*(3+n)))     end: seq(a(n), n=0..30); MATHEMATICA a[n_] := n!*(n*(n+7)/4 - 2*HarmonicNumber[n]); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 01 2017, from 2nd formula *) CROSSREFS Cf. A001008, A002805, A159324, A212396, A212397, A279683. Sequence in context: A037789 A037670 A037796 * A027141 A002398 A110065 Adjacent sequences:  A212392 A212393 A212394 * A212396 A212397 A212398 KEYWORD nonn AUTHOR Alois P. Heinz, May 14 2012 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.

Last modified May 19 14:36 EDT 2019. Contains 323395 sequences. (Running on oeis4.)