A334750 - OEIS

%I #26 Mar 16 2024 18:56:55

%S 0,0,4,16,103,711,5526,48066,463248,4908816,56749536,711299232,

%T 9609618816,139252708224,2154724104960,35464952597760,618712803717120,

%U 11405648080834560,221541001069731840,4522678391979417600,96811891510299033600,2168416142767145779200

%N Total number of swaps needed to sort all n! permutations of n elements by the optimal dual-pivot quicksort "Count".

%C The dual-pivot quicksort "Count" differs slightly from the original version of the dual-pivot quicksort algorithm of Aumüller et al. (2016, 2019). See Algorithm 1 in Neininger and Straub (2017, 2018).

%C By the design of the algorithm, for n >= 2, Neininger and Straub always require at least two swaps "at the end in order to bring the [two] pivots to their final positions".

%C Here a(n) is n! times the average number of swaps of the dual-pivot quicksort "Count" when sorting a random permutation of length n.

%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 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.

%F Recurrence: a(n)/n! = (6/(n*(n - 1))*Sum_{k=0..n-2} (n - k - 1)*a(k)/k! + 5*n/8 + 13/16 - 1/(16*(n - I[n is even])) for n >= 2 with a(0) = a(1) = 0, where I(condition) = 1 if the condition holds, and = 0 otherwise. [See p. 7 in Neininger and Straub (2017).]

%F a(n) = n!*((3/4)*n*Harmonic(n) + (1/20)*n*Harmonic_alt(n) - (4/5)*n + (3/4)*Harmonic(n) + (1/20)*Harmonic_alt(n) - 23/160 - (-1)^n/40 - ([n even]/320)*(1/(n - 3) + 3/(n - 1)) + ([n odd]/320)*(3/(n - 2) + 1/n)) for n >= 4, where Harmonic_alt(n) = Sum_{k=1..n} (-1)^n/n = -A058313(n)/A058312(n). [See Theorem 2.1 in Neininger and Straub (2017, 2018).]

%o (PARI)

%o lista(nn) = { nn = max(nn, 3); my(va = vector(nn)); va[1] = 0; va[2] = 4; for(n=3, nn, va[n] = n!*(6*sum(k=1, n-2, (n-k-1)*va[k]/k!)/(n*(n-1)) + 5*n/8 + 13/16 - 1/(16*(n - (1 + (-1)^n)/2)))); concat(0, va); };

%o (PARI)

%o H1(n) = sum(k=1, n, 1/k);

%o H2(n) = sum(k=1, n, (-1)^k/k);

%o H3(n) = if(0 == (n % 2), - (1/320)*(1/(n - 3) + 3/(n - 1)), (1/320)*(3/(n - 2) + 1/n));

%o lista(nn) = { nn = max(nn, 3); my(va = vector(nn)); va[1] = 0; va[2] = 4; va[3] = 16; for(n=4, nn, va[n] = n!*((3/4)*n*H1(n) + (1/20)*n*H2(n) - (4/5)*n + (3/4)*H1(n) + (1/20)*H2(n) - 23/160 - (-1)^n/40 + H3(n))); concat(0,va); };

%Y Cf. A058312, A058313, A288964, A288965, A288970, A288971.

%K nonn

%O 0,3

%A _Petros Hadjicostas_, May 09 2020