|
Search: id:A159324
|
|
|
| A159324 |
|
n! times the average number of comparisons required by an insertion sort of n (distinct) elements |
|
+0
2
|
|
| 0, 2, 16, 118, 926, 7956, 75132, 777456, 8771184, 107307360, 1416252960, 20068629120, 304002322560, 4903642679040, 83928856838400, 1519397749094400, 29010025797580800
(list; graph; listen)
|
|
|
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)
|
|
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: A037564 A125725 A162723 this_sequence A088755 A136782 A112710
Adjacent sequences: A159321 A159322 A159323 this_sequence A159325 A159326 A159327
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009
|
|
|
Search completed in 0.002 seconds
|
