cp's OEIS Frontend

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

%I A212396 #28 May 29 2018 09:25:11
%S A212396 0,0,3,23,41,313,73,676,3439,38231,46169,602359,703999,10565707,
%T A212396 12071497,13669093,30716561,582722017,215455199,4516351061,991731385,
%U A212396 361369795,393466951,9817955321,31848396101,858318957533,922672670033,8903430207697,9522990978097
%N A212396 Numerator of the average number of move operations required by an insertion sort of n (distinct) elements.
%C A212396 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.
%H A212396 Alois P. Heinz, <a href="/A212396/b212396.txt">Table of n, a(n) for n = 0..1000</a>
%H A212396 Wikipedia, <a href="https://en.wikipedia.org/wiki/Insertion_sort">Insertion sort</a>
%H A212396 <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%F A212396 a(n) = numerator of A212395(n)/A000142(n).
%F A212396 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).
%F A212396 a(n) = numerator of n*(n+7)/4 - 2*(Psi(n+1)+gamma) with digamma function Psi and the Euler-Mascheroni constant gamma = A001620.
%e A212396 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
%p A212396 b:= proc(n) option remember;
%p A212396       `if`(n=0, 0, b(n-1)*n + (n-1)! * (n-1)*(n+4)/2)
%p A212396     end:
%p A212396 a:= n-> numer(b(n)/n!):
%p A212396 seq(a(n), n=0..30);
%p A212396 # second Maple program:
%p A212396 a:= n-> numer(expand(n*(n+7)/4 -2*(Psi(n+1)+gamma))):
%p A212396 seq(a(n), n=0..30);
%t A212396 a[n_] := Numerator[n (n + 7)/4 - 2 HarmonicNumber[n]];
%t A212396 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, May 29 2018, from 2nd formula *)
%Y A212396 Denominators are in A212397.
%Y A212396 Cf. A000142, A001008, A001620, A002805, A212395.
%K A212396 nonn,frac
%O A212396 0,3
%A A212396 _Alois P. Heinz_, May 14 2012