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,3

Comments

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..448

Wikipedia, Insertion sort

Index entries for sequences related to sorting

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.

Example

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.

Maple

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

Mathematica

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

Crossrefs

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

Sequence in context: A037670 A037796 A331723 * A027141 A002398 A110065

Adjacent sequences: A212392 A212393 A212394 * A212396 A212397 A212398

Keyword

nonn

Author

Alois P. Heinz, May 14 2012

Status

approved