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
MAPLE
b:= proc(n) option remember;
`if`(n=0, 0, b(n-1)*n + (n-1)! * (n-1)*(n+4)/2)
end:
a:= n-> denom(b(n)/n!):
seq(a(n), n=0..30);
MATHEMATICA
a[n_] := Denominator[n (n + 7)/4 - 2 HarmonicNumber[n]];
Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, May 29 2018, from 2nd formula in A212396 *)
CROSSREFS
KEYWORD
nonn,frac
AUTHOR
_Alois P. Heinz_, May 14 2012
STATUS
approved