|
|
A212396
|
|
Numerator of the average number of move operations required by an insertion sort of n (distinct) elements.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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.
|
|
LINKS
|
|
|
FORMULA
|
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.
|
|
EXAMPLE
|
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
|
|
MAPLE
|
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);
|
|
MATHEMATICA
|
a[n_] := Numerator[n (n + 7)/4 - 2 HarmonicNumber[n]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|