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 *)
A279683
Number of move operations required to sort all permutations of [n] by MTF sort.
Original entry on oeis.org
0, 0, 1, 9, 78, 750, 8220, 102900, 1463280, 23451120, 419942880, 8331634080, 181689298560, 4323472433280, 111534141438720, 3101254066310400, 92468631077222400, 2943141763622860800, 99596858633182310400, 3570677764371119001600, 135190500045467682816000
Offset: 0
a(0) = a(1) = 0 because 0 or 1 elements are already sorted.
a(2) = 1: [1,2] is sorted and [2,1] needs one move.
a(3) = 9: [1,2,3](0), [1,3,2]->[2,1,3]->[1,2,3](2), [2,1,3]->[1,2,3](1), [2,3,1]->[1,2,3](1), [3,1,2]->[1,3,2]->[2,1,3]->[1,2,3](3), [3,2,1]->[2,3,1]->[1,2,3](2); sum of all moves gives 0+2+1+1+3+2 = 9.
-
a:= proc(n) option remember;
`if`(n=0, 0, a(n-1)*n + (n-1)! * (2^(n-1)-1))
end:
seq(a(n), n=0..20);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, [0$2, 1][n+1],
(4*n-3)*a(n-1)-(n-1)*(5*n-7)*a(n-2)+(2*n-2)*(n-2)^2*a(n-3))
end:
seq(a(n), n=0..20);
-
a[0] = 0; a[n_] := a[n] = a[n-1]*n + (n-1)!*(2^(n-1) - 1);
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 30 2018 *)
A212396
Numerator of the average number of move operations required by an insertion sort of n (distinct) elements.
Original entry on oeis.org
0, 0, 3, 23, 41, 313, 73, 676, 3439, 38231, 46169, 602359, 703999, 10565707, 12071497, 13669093, 30716561, 582722017, 215455199, 4516351061, 991731385, 361369795, 393466951, 9817955321, 31848396101, 858318957533, 922672670033, 8903430207697, 9522990978097
Offset: 0
0/1, 0/1, 3/2, 23/6, 41/6, 313/30, 73/5, 676/35, 3439/140, 38231/1260, 46169/1260, 602359/13860, 703999/13860 ... = A212396/A212397
-
b:= proc(n) option remember;
`if`(n=0, 0, b(n-1)*n + (n-1)! * (n-1)*(n+4)/2)
end:
a:= n-> numer(b(n)/n!):
seq(a(n), n=0..30);
# second Maple program:
a:= n-> numer(expand(n*(n+7)/4 -2*(Psi(n+1)+gamma))):
seq(a(n), n=0..30);
-
a[n_] := Numerator[n (n + 7)/4 - 2 HarmonicNumber[n]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 29 2018, from 2nd formula *)
A212397
Denominator of the average number of move operations required by an insertion sort of n (distinct) elements.
Original entry on oeis.org
1, 1, 2, 6, 6, 30, 5, 35, 140, 1260, 1260, 13860, 13860, 180180, 180180, 180180, 360360, 6126120, 2042040, 38798760, 7759752, 2586584, 2586584, 59491432, 178474296, 4461857400, 4461857400, 40156716600, 40156716600, 1164544781400, 1164544781400
Offset: 0
-
b:= proc(n) option remember;
`if`(n=0, 0, b(n-1)*n + (n-1)! * (n-1)*(n+4)/2)
end:
a:= n-> denom(b(n)/n!):
seq(a(n), n=0..30);
-
a[n_] := Denominator[n (n + 7)/4 - 2 HarmonicNumber[n]];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 29 2018, from 2nd formula in A212396 *)
Showing 1-4 of 4 results.
Comments