cp's OEIS Frontend

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

%I A159323 #10 Jun 01 2021 12:01:07
%S A159323 0,0,2,12,4,48,40,24,6,160,216,224,182,96,40,8,480,896,1248,1440,1386,
%T A159323 1100,738,416,182,60,10,1344,3200,5472,7776,9588,10528,10200,8932,
%U A159323 7046,4992,3124,1720,810,304,84,12
%N A159323 Triangle read by rows: T(n,k) = A129178(n,k) * (n*(n-1)/2 - k).
%C A159323 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).
%H A159323 Alois P. Heinz, <a href="/A159323/b159323.txt">Rows n = 0..50, flattened</a>
%F A159323 a(n,k) = A129178(n,k) * (n(n-1)/2 - k).
%e A159323 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.
%e A159323 Triangle T(n,k) begins:
%e A159323     0;
%e A159323     0;
%e A159323     2;
%e A159323    12,   4;
%e A159323    48,  40,   24,    6;
%e A159323   160, 216,  224,  182,   96,   40,   8;
%e A159323   480, 896, 1248, 1440, 1386, 1100, 738, 416, 182, 60, 10;
%e A159323   ...
%p A159323 s:= proc(n) option remember; `if`(n<0, 1, `if`(n=0, 2, t^n+s(n-1))) end:
%p A159323 p:= proc(n) option remember; `if`(n<0, 1, expand(s(n-2)*p(n-1))) end:
%p A159323 T:= n-> (h-> seq(coeff(h,t,i)*(n*(n-1)/2-i), i=0..degree(h)))(p(n)):
%p A159323 seq(T(n), n=0..8);  # _Alois P. Heinz_, Dec 16 2016
%t A159323 s[n_] := s[n] = If[n < 0, 1, If[n == 0, 2, t^n + s[n - 1]]];
%t A159323 p[n_] := p[n] = If[n < 0, 1, Expand[s[n - 2]*p[n - 1]]];
%t A159323 T[n_] := Function[h, Table[Coefficient[h, t, i]*(n*(n - 1)/2 - i), {i, 0, Exponent[h, t]}]][p[n]];
%t A159323 Table[T[n], {n, 0, 8}] // Flatten (* _Jean-François Alcover_, Apr 06 2017, after _Alois P. Heinz_ *)
%K A159323 nonn,tabl
%O A159323 0,3
%A A159323 Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009
%E A159323 One term for row n=0 prepended by _Alois P. Heinz_, Dec 16 2016