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

 

Logo


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

Index entries for sequences related to sorting

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 25 03:50 EDT 2019. Contains 324338 sequences. (Running on oeis4.)