login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A159323 Triangle read by rows: T(n,k) = A129178(n,k) * (n*(n-1)/2 - k). 3
0, 0, 2, 12, 4, 48, 40, 24, 6, 160, 216, 224, 182, 96, 40, 8, 480, 896, 1248, 1440, 1386, 1100, 738, 416, 182, 60, 10, 1344, 3200, 5472, 7776, 9588, 10528, 10200, 8932, 7046, 4992, 3124, 1720, 810, 304, 84, 12 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Summing the rows and dividing by n! gives the average number of comparisons required by a insertion sort on n (distinct) elements. Each entry in the triangle gives the separate contribution of permutations that require (n(n-1)/2 - k) comparisons (i.e. we start with the one taking most comparisons and work down to the one taking least).

LINKS

Alois P. Heinz, Rows n = 0..50, flattened

FORMULA

a(n,k) = A129178(n,k) * (n(n-1)/2 - k).

EXAMPLE

For n=3, permutations 123, 132, 213 and 312 require three comparisons to sort, and permutations 231 and 321 require two. So a(3,0) = 4*3 = 12, and a(3,1) = 2*2 = 4.

Triangle T(n,k) begins:

    0;

    0;

    2;

   12,   4;

   48,  40,   24,    6;

  160, 216,  224,  182,   96,   40,   8;

  480, 896, 1248, 1440, 1386, 1100, 738, 416, 182, 60, 10;

  ...

MAPLE

s:= proc(n) option remember; `if`(n<0, 1, `if`(n=0, 2, t^n+s(n-1))) end:

p:= proc(n) option remember; `if`(n<0, 1, expand(s(n-2)*p(n-1))) end:

T:= n-> (h-> seq(coeff(h, t, i)*(n*(n-1)/2-i), i=0..degree(h)))(p(n)):

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

MATHEMATICA

s[n_] := s[n] = If[n < 0, 1, If[n == 0, 2, t^n + s[n - 1]]];

p[n_] := p[n] = If[n < 0, 1, Expand[s[n - 2]*p[n - 1]]];

T[n_] := Function[h, Table[Coefficient[h, t, i]*(n*(n - 1)/2 - i), {i, 0, Exponent[h, t]}]][p[n]];

Table[T[n], {n, 0, 8}] // Flatten (* Jean-Fran├žois Alcover, Apr 06 2017, after Alois P. Heinz *)

CROSSREFS

Sequence in context: A164857 A326125 A066700 * A038218 A264841 A191249

Adjacent sequences:  A159320 A159321 A159322 * A159324 A159325 A159326

KEYWORD

nonn,tabl

AUTHOR

Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009

EXTENSIONS

One term for row n=0 prepended by Alois P. Heinz, Dec 16 2016

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 21 18:50 EDT 2021. Contains 345365 sequences. (Running on oeis4.)