This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A212396 Numerator of the average number of move operations required by an insertion sort of n (distinct) elements. 3
 0, 0, 3, 23, 41, 313, 73, 676, 3439, 38231, 46169, 602359, 703999, 10565707, 12071497, 13669093, 30716561, 582722017, 215455199, 4516351061, 991731385, 361369795, 393466951, 9817955321, 31848396101, 858318957533, 922672670033, 8903430207697, 9522990978097 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS The average number of move operations is 1/n! times the number of move operations required to sort all permutations of [n] (A212395), assuming that each permutation is equiprobable. LINKS Alois P. Heinz, Table of n, a(n) for n = 0..1000 Wikipedia, Insertion sort FORMULA a(n) = numerator of A212395(n)/A000142(n). a(n) = numerator of 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) = numerator of n*(n+7)/4 - 2*(Psi(n+1)+gamma) with digamma function Psi and the Euler-Mascheroni constant gamma = A001620. EXAMPLE 0/1, 0/1, 3/2, 23/6, 41/6, 313/30, 73/5, 676/35, 3439/140, 38231/1260, 46169/1260, 602359/13860, 703999/13860 ... = A212396/A212397 MAPLE b:= proc(n) option remember;       `if`(n=0, 0, b(n-1)*n + (n-1)! * (n-1)*(n+4)/2)     end: a:= n-> numer(b(n)/n!): seq(a(n), n=0..30); # second Maple program: a:= n-> numer(expand(n*(n+7)/4 -2*(Psi(n+1)+gamma))): seq(a(n), n=0..30); MATHEMATICA a[n_] := Numerator[n (n + 7)/4 - 2 HarmonicNumber[n]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 29 2018, from 2nd formula *) CROSSREFS Denominators are in A212397. Cf. A000142, A001008, A001620, A002805, A212395. Sequence in context: A106066 A281551 A167216 * A319976 A117738 A014582 Adjacent sequences:  A212393 A212394 A212395 * A212397 A212398 A212399 KEYWORD nonn,frac 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 June 25 03:50 EDT 2019. Contains 324338 sequences. (Running on oeis4.)