login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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, 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 Cominatorics, New Orleans, Louisiana, USA, 7pp.

Index entries for sequences related to sorting

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

Cf. A058312, A058313, A288964, A288970, A288971.

Sequence in context: A288970 A037564 A125725 * A207420 A207736 A208364

Adjacent sequences:  A288962 A288963 A288964 * A288966 A288967 A288968

KEYWORD

nonn

AUTHOR

Daniel Krenn, Jun 20 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 9 02:53 EDT 2021. Contains 343685 sequences. (Running on oeis4.)