A212397 - OEIS

%I #21 May 29 2018 09:25:03

%S 1,1,2,6,6,30,5,35,140,1260,1260,13860,13860,180180,180180,180180,

%T 360360,6126120,2042040,38798760,7759752,2586584,2586584,59491432,

%U 178474296,4461857400,4461857400,40156716600,40156716600,1164544781400,1164544781400

%N Denominator of the average number of move operations required by an insertion sort of n (distinct) elements.

%C 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 Alois P. Heinz, <a href="/A212397/b212397.txt">Table of n, a(n) for n = 0..1000</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Insertion_sort">Insertion sort</a>

%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>

%F a(n) = denominator of A212395(n)/A000142(n).

%p b:= proc(n) option remember;

%p       `if`(n=0, 0, b(n-1)*n + (n-1)! * (n-1)*(n+4)/2)

%p     end:

%p a:= n-> denom(b(n)/n!):

%p seq(a(n), n=0..30);

%t a[n_] := Denominator[n (n + 7)/4 - 2 HarmonicNumber[n]];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, May 29 2018, from 2nd formula in A212396 *)

%Y Numerators are in A212396.

%Y Cf. A000142, A212395.

%K nonn,frac

%O 0,3

%A _Alois P. Heinz_, May 14 2012