cp's OEIS Frontend

A334935 The product of (n!)^2/8 and the variance of the random number of comparisons needed to sort a list of n distinct items using quicksort.

%I A334935 #8 May 17 2020 05:22:28
%S A334935 0,0,0,1,58,3312,219528,17445312,1665090432,189515635200,
%T A334935 25472408256000,4002577182720000,728259627506688000,
%U A334935 152076300005855232000,36154290403284480000000,9714114050265240698880000,2930311008702414783774720000,986466808456816565267988480000,368586443487759607372452986880000
%N A334935 The product of (n!)^2/8 and the variance of the random number of comparisons needed to sort a list of n distinct items using quicksort.
%H A334935 S. B. Ekhad and D. Zeilberger, <a href="https://arxiv.org/abs/1903.03708">A detailed analysis of quicksort running time</a>, arXiv:1903.03708 [math.PR], 2019; see Theorem 2.
%H A334935 V. Iliopoulos, <a href="https://arxiv.org/abs/1503.02504">The quicksort algorithm and related topics</a>, arXiv:1503.02504 [cs.DS], 2015.
%H A334935 V. Iliopoulos and D. Penman, <a href="https://arxiv.org/abs/1006.4063">Variance of the number of comparisons of randomized quicksort</a>, arXiv:1006.4063 [math.PR], 2010.
%F A334935 a(n) = ((n!)^2/8)*A330895(n)/A330907(n).
%F A334935 a(n) = ((n!)^2/8)*(n*(7*n + 13) - 2*(n + 1)*Sum_{k=1..n} 1/k - 4*(n + 1)^2*Sum_{k=1..n} 1/k^2).
%o A334935 (PARI) lista(nn) = {my(va = vector(nn)); for(n=1, nn, va[n] = ((n!)^2/8)*(n*(7*n+13) - 2*(n+1)*sum(k=1, n, 1/k) - 4*(n+1)^2*sum(k=1, n, 1/k^2))); concat(0, va); }
%Y A334935 Cf. A330895, A330907.
%K A334935 nonn
%O A334935 0,5
%A A334935 _Petros Hadjicostas_, May 16 2020