|
%I #66 Mar 16 2024 18:59:27
%S 0,0,2,16,114,866,7188,65580,655872,7157376,84775680,1084343040,
%T 14906039040,219267751680,3437854963200,57247256424960,
%U 1009189972869120,18779054120386560,367876307230064640,7568437652936294400,163164173556503347200,3678547646214424166400
%N Number of key comparisons to sort all n! permutations of n elements by the optimal dual-pivot quicksort.
%H Daniel Krenn, <a href="/A288965/b288965.txt">Table of n, a(n) for n = 0..100</a>
%H M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, <a href="https://arxiv.org/abs/1611.00258">Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths</a>, arXiv:1611.00258 [math.CO], 2016.
%H M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, <a href="https://doi.org/10.1017/S096354831800041X">Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths</a>, Combin. Probab. Comput. 28(4) (2019), 485-518.
%H Daniel Krenn, <a href="https://github.com/dkrenn/quickstar">Quickstar</a>, Program in SageMath, on GitHub.
%H R. Neininger and J. Straub, <a href="https://arxiv.org/abs/1710.07505">Probabilistic analysis of the dual-pivot quicksort "count"</a>, arXiv:1710.07505 [cs.DS], 2017.
%H R. Neininger and J. Straub, <a href="https://doi.org/10.1137/1.9781611975062.1">Probabilistic analysis of the dual-pivot quicksort "count"</a>, 2018 Proceedings of the Meeting of Analytic Algorithmics and Combinatorics, New Orleans, Louisiana, USA, 7pp.
%H <a href="/index/So#sorting">Index entries for sequences related to sorting</a>
%F 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
%p haralt := proc(n) local k: add((-1)^k/k, k = 1 .. n): end proc:
%p 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:
%p 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:
%p if 0 = n mod 2 then v2 := -1/320*1/(n - 3) - 3/320*1/(n - 1): end if:
%p if 1 = n mod 2 then v2 := 3/320*1/(n - 2) + 1/320*1/n: end if:
%p v := n!*(v1 + v2): end if: v: end proc:
%p seq(a(n1), n1 = 0 .. 30); # _Petros Hadjicostas_, May 03 2020
%t haralt[n_] := Sum[(-1)^k/k, {k, 1, n}];
%t 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))];
%t a /@ Range[0, 21] (* _Jean-François Alcover_, Jun 05 2020 *)
%o (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)
%Y Cf. A058312, A058313, A288964, A288970, A288971.
%K nonn
%O 0,3
%A _Daniel Krenn_, Jun 20 2017
|
