A159323 Triangle read by rows: T(n,k) = A129178(n,k) * (n*(n-1)/2 - k).

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

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