|
| |
|
|
A159324
|
|
n! times the average number of comparisons required by an insertion sort of n (distinct) elements
|
|
2
| |
|
|
0, 2, 16, 118, 926, 7956, 75132, 777456, 8771184, 107307360, 1416252960, 20068629120, 304002322560, 4903642679040, 83928856838400, 1519397749094400, 29010025797580800
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
FORMULA
| a(n) = a(n-1)*(n) + n! (n+1)/2 - (n-1)!
a(n) = Sum_k A159323(n,k) = Sum_k A129178(n,k) * (n(n-1)/2 - k)
a(n) = n!/4 *(n^2+3n-4h(n)), where h(n) = sum(1/k,k=1..n) [From Gary Detlefs (gdetlefs(AT)aol.com), Sep 02 2010]
|
|
|
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.
|
|
|
CROSSREFS
| Row sums of triangle A159323
Sequence in context: A125725 A162723 A193289 * A088755 A136782 A112710
Adjacent sequences: A159321 A159322 A159323 * A159325 A159326 A159327
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009
|
| |
|
|
