OFFSET
0,3
LINKS
Daniel Krenn, Table of n, a(n) for n = 0..100
M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths, arXiv:1611.00258 [math.CO], 2016.
M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths, Combin. Probab. Comput. 28(4) (2019), 485-518.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
R. Neininger and J. Straub, Probabilistic analysis of the dual-pivot quicksort "count", arXiv:1710.07505 [cs.DS], 2017.
R. Neininger and J. Straub, Probabilistic analysis of the dual-pivot quicksort "count", 2018 Proceedings of the Meeting of Analytic Algorithmics and Combinatorics, New Orleans, Louisiana, USA, 7pp.
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:
seq(a(n1), n1 = 0 .. 30); # Petros Hadjicostas, May 03 2020
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))];
a /@ Range[0, 21] (* Jean-François Alcover, Jun 05 2020 *)
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
Daniel Krenn, Jun 20 2017
STATUS
approved