A159323
Triangle read by rows: T(n,k) = A129178(n,k) * (n*(n-1)/2 - k).
Original entry on oeis.org
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
Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009
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;
...
-
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
-
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 *)
A159324
n! times the average number of comparisons required by an insertion sort of n (distinct) elements.
Original entry on oeis.org
0, 0, 2, 16, 118, 926, 7956, 75132, 777456, 8771184, 107307360, 1416252960, 20068629120, 304002322560, 4903642679040, 83928856838400, 1519397749094400, 29010025797580800, 582647327132774400, 12280347845905305600, 271030782903552000000, 6251213902855219200000
Offset: 0
Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009
For n=3, insertion sorting 123, 213, 213, 231, 312, 321 takes 3+3+3+2+3+2 = 4*3+2*2 = 16 comparisons.
-
a:= proc(n) option remember;
`if`(n<2, 0, a(n-1)*n + (n-1)! * (n-1)*(n+2)/2)
end:
seq(a(n), n=0..30); # Alois P. Heinz, May 14 2012
# second Maple program:
a:= proc(n) option remember; `if`(n<3, [0$2, 2][n+1],
((2*n^3-n^2-5*n+2)*a(n-1)-(n+2)*(n-1)^3*a(n-2))/((n-2)*(n+1)))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Dec 16 2016
-
a[n_] := n! ((n+1)(n+2)/4 - HarmonicNumber[n] - 1/2); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Apr 12 2017, after Gary Detlefs *)
Original entry on oeis.org
0, 2, 26, 274, 2844, 30708, 351504, 4292496, 55988640, 779171040, 11545476480, 181705299840, 3029581820160, 53376951801600, 991337037465600, 19363464423475200, 396915849843609600, 8520964324004966400, 191220598650009600000, 4477883953203763200000, 109242544826541772800000
Offset: 2
- L. Carlitz, Generalized Stirling numbers, Combinatorial Analysis Notes, Duke University, 1968, 1-7.
-
[Factorial(n)*(n*(n-5)/4 + HarmonicNumber(n)): n in [2..25]]; // G. C. Greubel, May 05 2019
-
seq(n!*(sum(1/k, k = 1 .. n)+(1/4)*n*(n-5)), n = 2 .. 21); # Emeric Deutsch, Oct 10 2007
-
Table[n!*(n*(n-5)/4 + HarmonicNumber[n]), {n,2,25}] (* G. C. Greubel, May 05 2019 *)
-
my(x='x+O('x^30)); concat([0], Vec(serlaplace( (2*x - 3*x^2 + 2*(1-x)^2*log(1-x))/(2*(-1+x)^3) ))) \\ G. C. Greubel, May 05 2019
-
[factorial(n)*(n*(n-5)/4 + harmonic_number(n)) for n in (2..25)] # G. C. Greubel, May 05 2019
A159325
Median number of comparisons used by insertion sort on n (distinct) elements.
Original entry on oeis.org
0, 1, 3, 5, 8, 11, 15, 19, 24, 30, 36, 42, 49, 56, 64, 73, 82, 91, 101, 111, 122, 134, 146, 158, 171, 185
Offset: 1
Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009
For n=3, permutations 123,132,213,231,312,321 require 3,3,3,2,3,2 comparisons respectively, so the median is 3.
Showing 1-4 of 4 results.
Comments