|
|
A288965
|
|
Number of key comparisons to sort all n! permutations of n elements by the optimal dual-pivot quicksort.
|
|
15
|
|
|
0, 0, 2, 16, 114, 866, 7188, 65580, 655872, 7157376, 84775680, 1084343040, 14906039040, 219267751680, 3437854963200, 57247256424960, 1009189972869120, 18779054120386560, 367876307230064640, 7568437652936294400, 163164173556503347200, 3678547646214424166400
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
|
|
FORMULA
|
a(n) = n!*((9/5)*n*Harmonic(n) - (1/5)*n*Harmonic_alt(n) - (89/25)*n + (67/40)*Harmonic(n) - (3/40)*Harmonic_alt(n) - 83/800 + (-1)^n/10 - ([n even]/320)*(1/(n - 3) + 3/(n - 1)) + ([n odd]/320)*(3/(n - 2) + 1/n)) for n >= 4, where [condition] = 1 if the condition holds, and 0 otherwise, and Harmonic_alt(n) = Sum_{k=1..n} (-1)^n/n = -A058313(n)/A058312(n). [This follows from Theorem 12.1 in Aumüller et al. (2016) or Theorem 5.7 in Aumüller et al. (2019).] - Petros Hadjicostas, May 03 2020
|
|
MAPLE
|
haralt := proc(n) local k: add((-1)^k/k, k = 1 .. n): end proc:
a := proc(n) local v, v1, v2: if n = 0 or n = 1 then v := 0: end if; if n = 2 then v := 2: end if: if n = 3 then v := 16: end if:
if 4 <= n then v1 := 9/5*n*harmonic(n) - 1/5*n*haralt(n) - 89/25*n + 67/40*harmonic(n) - 3/40*haralt(n) - 83/800 + 1/10*(-1)^n:
if 0 = n mod 2 then v2 := -1/320*1/(n - 3) - 3/320*1/(n - 1): end if:
if 1 = n mod 2 then v2 := 3/320*1/(n - 2) + 1/320*1/n: end if:
v := n!*(v1 + v2): end if: v: end proc:
|
|
MATHEMATICA
|
haralt[n_] := Sum[(-1)^k/k, {k, 1, n}];
a[n_] := Switch[n, 0|1, 0, 2, 2, 3, 16, _, n! ((9/5) n HarmonicNumber[n] - (1/5) n haralt[n] - (89/25) n + (67/40) HarmonicNumber[n] - (3/40)* haralt[n] - 83/800 + (-1)^n/10 - (Boole[EvenQ[n]]/320)(1/(n-3) + 3/(n-1)) + (Boole[OddQ[n]]/320)(3/(n-2) + 1/n))];
|
|
PROG
|
(PARI) lista(nn) = {my(x='x + O('x^nn)); concat([0, 0], Vec(serlaplace(-8*log(1-x)/(5*(1-x)^2) + 2*atanh(x)/(5*(1-x)^2) - 44/(25*(1-x)^2) - atanh(x)/(4*(1-x)) + 281/(160*(1-x)) + ((1-x)^3/320)*atanh(x) + x^3/150 - 27*x^2/1600 + 17*x/1600 + 3/800)))}; \\ Petros Hadjicostas and Michel Marcus, May 04 2020, e.g.f. from p. 29 in Aumüller et al. (2016)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|