A212396 -id:A212396 - 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.

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

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.

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

Numerators are in A212396.

Cf. A000142, A212395.

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

a(n) = denominator of A212395(n)/A000142(n).

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