A212397 -id:A212397 - cp's OEIS frontend

A212395 Number of move operations required to sort all permutations of [n] by insertion sort.

0, 0, 3, 23, 164, 1252, 10512, 97344, 990432, 11010528, 132966720, 1734793920, 24330205440, 365150833920, 5840673108480, 99204809356800, 1783428104908800, 33833306484633600, 675513065777356800, 14160039606855475200, 310935875030323200000

Offset: 0

Alois P. Heinz, May 14 2012

nonn

a(n) is n! times the average number of move operations (A212396, A212397) required by an insertion sort of n (distinct) elements.

			a(0) = a(1) = 0 because 0 or 1 elements are already sorted.
a(2) = 3: [1,2] is sorted and [2,1] needs 3 moves.
a(3) = 23: [1,2,3]->(0), [1,3,2]->(3), [2,1,3]->(3), [2,3,1]->(4), [3,1,2]->(6), [3,2,1]->(7); sum of all moves gives 0+3+3+4+6+7 = 23.

Alois P. Heinz, Table of n, a(n) for n = 0..448
Wikipedia, Insertion sort
Index entries for sequences related to sorting

Cf. A001008, A002805, A159324, A212396, A212397, A279683.

a:= proc(n) option remember;
      `if`(n=0, 0, a(n-1)*n + (n-1)! * (n-1)*(n+4)/2)
    end:
seq(a(n), n=0..30);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, [0$2, 3][n+1],
      ((2*n^3+3*n^2-13*n+4)*a(n-1) -(n+4)*
       (n-1)^3*a(n-2)) / ((n-2)*(3+n)))
    end:
seq(a(n), n=0..30);

a[n_] := n!*(n*(n+7)/4 - 2*HarmonicNumber[n]); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 01 2017, from 2nd formula *)

a(n) = a(n-1)*n + (n-1)! * (n-1)*(n+4)/2 for n>0, a(0) = 0.
a(n) = n! * (n*(n+7)/4 - 2*H(n)) with n-th harmonic number H(n) = Sum_{k=1..n} 1/k = A001008(n)/A002805(n).
a(n) = ((2*n^3+3*n^2-13*n+4)*a(n-1)-(n+4)*(n-1)^3*a(n-2))/((n-2)*(3+n)) for n>2.

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

Alois P. Heinz, May 14 2012

The average number of move operations is 1/n! times the number of move operations required to sort all permutations of [n] (A212395), assuming that each permutation is equiprobable.

			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

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Wikipedia, Insertion sort
Index entries for sequences related to sorting

Denominators are in A212397.

Cf. A000142, A001008, A001620, A002805, A212395.

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

a(n) = numerator of A212395(n)/A000142(n).
a(n) = numerator of n*(n+7)/4 - 2*H(n) with n-th harmonic number H(n) = Sum_{k=1..n} 1/k = A001008(n)/A002805(n).
a(n) = numerator of n*(n+7)/4 - 2*(Psi(n+1)+gamma) with digamma function Psi and the Euler-Mascheroni constant gamma = A001620.

cp's OEIS Frontend

A212395 Number of move operations required to sort all permutations of [n] by insertion sort.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula