The OEIS is supported by the many generous donors to the OEIS Foundation.

 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 13 16:51 EDT 2024. Contains 375144 sequences. (Running on oeis4.)