A212396 Numerator of the average number of move operations required by an insertion sort of n (distinct) elements.

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

Offset: 0

Author

Alois P. Heinz, May 14 2012

Keywords

• nonn
• frac

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.

Examples

			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
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Wikipedia, Insertion sort
• Index entries for sequences related to sorting

Crossrefs

Denominators are in A212397.

Cf. A000142, A001008, A001620, A002805, A212395.

Programs

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 *)

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.