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