|
|
A159324
|
|
n! times the average number of comparisons required by an insertion sort of n (distinct) elements.
|
|
9
|
|
|
0, 0, 2, 16, 118, 926, 7956, 75132, 777456, 8771184, 107307360, 1416252960, 20068629120, 304002322560, 4903642679040, 83928856838400, 1519397749094400, 29010025797580800, 582647327132774400, 12280347845905305600, 271030782903552000000, 6251213902855219200000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
FORMULA
|
a(n) = a(n-1)*(n) + n! *(n+1)/2 - (n-1)!.
a(n) = n!/4 *(n^2+3*n-4*H(n)), where H(n) = Sum_{k=1..n} 1/k. - Gary Detlefs, Sep 02 2010
a(n) = ((2*n^3-n^2-5*n+2)*a(n-1)-(n+2)*(n-1)^3*a(n-2))/((n-2)*(n+1)) for n>2. - Alois P. Heinz, Dec 16 2016
|
|
EXAMPLE
|
For n=3, insertion sorting 123, 213, 213, 231, 312, 321 takes 3+3+3+2+3+2 = 4*3+2*2 = 16 comparisons.
|
|
MAPLE
|
a:= proc(n) option remember;
`if`(n<2, 0, a(n-1)*n + (n-1)! * (n-1)*(n+2)/2)
end:
# second Maple program:
a:= proc(n) option remember; `if`(n<3, [0$2, 2][n+1],
((2*n^3-n^2-5*n+2)*a(n-1)-(n+2)*(n-1)^3*a(n-2))/((n-2)*(n+1)))
end:
|
|
MATHEMATICA
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009
|
|
STATUS
|
approved
|
|
|
|