A330907 Denominator of the variance of the random number of comparisons in quicksort applied to lists of length n.

1, 1, 1, 9, 36, 25, 900, 11025, 19600, 15876, 317520, 53361, 38419920, 33127380, 144288144, 2029052025, 129859329600, 115831315600, 37529346254400, 33870234994596, 6144260316480, 799769421360, 387088399938240, 355503061748835, 40953952713465792, 37864231428870000, 316002721554520000, 2056839142975402500, 1612561888092715560000

Offset: 0

Author

Petros Hadjicostas, May 01 2020

Keywords

• nonn
• frac

Examples

			The variances are: 0, 0, 0, 2/9, 29/36, 46/25, 3049/900, 60574/11025, 160599/19600, 182789/15876, 4913659/317520, 1072364/53361, ... = A330895/A330907.
		

References

• D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 1973; see answer to Ex. 8(a) of Section 6.2.2.

Links

• S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019; see Theorem 2.
• V. Iliopoulos, The quicksort algorithm and related topics, arXiv:1503.02504 [cs.DS], 2015.
• V. Iliopoulos and D. Penman, Variance of the number of comparisons of randomized quicksort, arXiv:1006.4063 [math.PR], 2010.

Crossrefs

Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A329001, A330852, A330860, A330875, A330876, A330895 (numerators).

Programs

Maple

a := n -> denom(2*(n+1)*(harmonic(n,1) + 2*(n+1)*harmonic(n,2))):
seq(a(n), n=0..28); # Peter Luschny, May 02 2020

PARI

lista(nn) = {my(va = vector(nn)); for(n=1, nn, va[n] = denominator(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(1, va); }

Formula

a(n) = denominator(fr(n)), where fr(n) = n*(7*n + 13) - 2*(n+1)*Sum_{k=1..n} (1/k) - 4*(n+1)^2*Sum_{k=1..n} (1/k^2).

a(n) = denominator(2*(n+1)*(H(n,1) + 2*(n+1)*H(n,2))), where H(n,s) are the generalized harmonic numbers. - Peter Luschny, May 02 2020