This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A334750 #29 Mar 20 2025 04:21:51
%S A334750 0,0,4,16,103,711,5526,48066,463248,4908816,56749536,711299232,
%T A334750 9609618816,139252708224,2154724104960,35464952597760,618712803717120,
%U A334750 11405648080834560,221541001069731840,4522678391979417600,96811891510299033600,2168416142767145779200
%N A334750 Total number of swaps needed to sort all n! permutations of n elements by the optimal dual-pivot quicksort "Count".
%C A334750 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 A334750 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 A334750 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 A334750 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 A334750 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 A334750 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 A334750 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 A334750 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 A334750 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 A334750 (PARI)
%o A334750 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 A334750 (PARI)
%o A334750 H1(n) = sum(k=1, n, 1/k);
%o A334750 H2(n) = sum(k=1, n, (-1)^k/k);
%o A334750 H3(n) = if(0 == (n % 2), - (1/320)*(1/(n - 3) + 3/(n - 1)), (1/320)*(3/(n - 2) + 1/n));
%o A334750 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 A334750 Cf. A058312, A058313, A288964, A288965, A288970, A288971.
%K A334750 nonn
%O A334750 0,3
%A A334750 _Petros Hadjicostas_, May 09 2020