login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Alois P. Heinz, Table of n, a(n) for n = 0..448

Wikipedia, Insertion sort

Index entries for sequences related to sorting

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+3*n-4*H(n)), where H(n) = Sum_{k=1..n} 1/k. - Gary Detlefs, Sep 02 2010

a(n) = A138772(n+1) - A000254(n). - Gary Detlefs, May 13 2012

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

a(n) = 2 * A285231(n+1). - Alois P. Heinz, Apr 15 2017

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:

seq(a(n), n=0..30); # Alois P. Heinz, May 14 2012

# 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:

seq(a(n), n=0..30); # Alois P. Heinz, Dec 16 2016

MATHEMATICA

a[n_] := n! ((n+1)(n+2)/4 - HarmonicNumber[n] - 1/2); Table[a[n], {n, 0, 30}] (* Jean-Fran├žois Alcover, Apr 12 2017, after Gary Detlefs *)

CROSSREFS

Row sums of triangle A159323.

Cf. A138772, A000254, A212395, A285231.

Sequence in context: A162723 A288964 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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 16 06:46 EDT 2019. Contains 324145 sequences. (Running on oeis4.)