|
%I #34 Jun 21 2017 18:52:18
%S 0,0,3,23,164,1252,10512,97344,990432,11010528,132966720,1734793920,
%T 24330205440,365150833920,5840673108480,99204809356800,
%U 1783428104908800,33833306484633600,675513065777356800,14160039606855475200,310935875030323200000
%N Number of move operations required to sort all permutations of [n] by insertion sort.
%C a(n) is n! times the average number of move operations (A212396, A212397) required by an insertion sort of n (distinct) elements.
%H Alois P. Heinz, <a href="/A212395/b212395.txt">Table of n, a(n) for n = 0..448</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) = a(n-1)*n + (n-1)! * (n-1)*(n+4)/2 for n>0, a(0) = 0.
%F a(n) = n! * (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 a(n) = ((2*n^3+3*n^2-13*n+4)*a(n-1)-(n+4)*(n-1)^3*a(n-2))/((n-2)*(3+n)) for n>2.
%e a(0) = a(1) = 0 because 0 or 1 elements are already sorted.
%e a(2) = 3: [1,2] is sorted and [2,1] needs 3 moves.
%e a(3) = 23: [1,2,3]->(0), [1,3,2]->(3), [2,1,3]->(3), [2,3,1]->(4), [3,1,2]->(6), [3,2,1]->(7); sum of all moves gives 0+3+3+4+6+7 = 23.
%p a:= proc(n) option remember;
%p `if`(n=0, 0, a(n-1)*n + (n-1)! * (n-1)*(n+4)/2)
%p end:
%p seq(a(n), n=0..30);
%p # second Maple program:
%p a:= proc(n) option remember; `if`(n<3, [0$2, 3][n+1],
%p ((2*n^3+3*n^2-13*n+4)*a(n-1) -(n+4)*
%p (n-1)^3*a(n-2)) / ((n-2)*(3+n)))
%p end:
%p seq(a(n), n=0..30);
%t a[n_] := n!*(n*(n+7)/4 - 2*HarmonicNumber[n]); Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Feb 01 2017, from 2nd formula *)
%Y Cf. A001008, A002805, A159324, A212396, A212397, A279683.
%K nonn
%O 0,3
%A _Alois P. Heinz_, May 14 2012
|
