A330860 Denominator of the rational number A(n) that appears in the formula for the n-th cumulant k(n) = (-1)^n*2^n*(A(n) - (n - 1)!*zeta(n)) of the limiting distribution of the number of comparisons in quicksort, for n >= 2, with A(0) = 1 and A(1) = 0.

1, 1, 4, 8, 144, 3456, 172800, 10368000, 3810240000, 177811200000, 9957427200000, 75278149632000000, 1912817782149120000000, 53023308921173606400000000, 17742659631203112173568000000000, 426249654980023566857797632000000000, 9600207854287580784554747166720000000000

Offset: 0

Author

Petros Hadjicostas, Apr 28 2020

Keywords

• nonn
• frac

Comments

Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.

First he calculates the numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, given for p >= 0 by the recurrence

Sum_{r=0..p} Stirling1(p+2, r+1)*B(p-r)/(p-r)! + Sum_{r=0..p} F(r)*F(p-r) = 0, where F(r) = Sum_{i=0..r} Stirling1(r+1,i+1)*G(r-i) and G(k) = Sum_{a=0..k} (-1)^a*B(k-a)/(a!*(k-a)!*2^a).

Then A(n) = L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.

Hoffman and Kuba (2019, 2020) gave an alternative proof of Hennequin's cumulant formula and gave an alternative calculation for the constants (-2)^n*A(n), which they denote by a_n. See also Finch (2020).

The Maple program given in A330852 is based on Tan and Hadjicostas (1993), where the numbers (A(n): n >= 0) are also tabulated.

For a list of references about the theory of the limiting distribution of the number of comparisons in quicksort, which we do not discuss here, see the ones for sequence A330852.

Examples

			The first few fractions A(n) are
1, 0, 7/4, 19/8, 937/144, 85981/3456, 21096517/172800, 7527245453/10368000, 19281922400989/3810240000, 7183745930973701/177811200000, ...
The first few fractions (-2)^n*A(n) (= a_n in Hoffman and Kuba and in Finch) are
1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ...
		

References

• Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991), p. 83.

Links

• Petros Hadjicostas, Table of n, a(n) for n = 0..30
• S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019. [They have the first eight moments for the number of comparisons in quicksort from which Hennequin's first eight asymptotic cumulants can be derived.]
• Steven Finch, Recursive PGFs for BSTs and DSTs, arXiv:2002.02809 [cs.DS], 2020; see Section 1.4. [He gives the constants a_s = (-2)^s*A(s) for s >= 2.]
• P. Hennequin, Combinatorial analysis of the quicksort algorithm, Informatique théoretique et applications, 23(3) (1989), 317-333.
• M. E. Hoffman and M. Kuba, Logarithmic integrals, zeta values, and tiered binomial coefficients, arXiv:1906.08347 [math.CO], 2019-2020; see Section 5.2. [They study the constants a_s = (-2)^s*A(s) for s >= 2.]
• Kok Hooi Tan and Petros Hadjicostas, Density and generating functions of a limiting distribution in quicksort, Technical Report #568, Department of Statistics, Carnegie Mellon University, Pittsburgh, PA, USA, 1993; see p. 10.

Crossrefs

Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A330852 (numerators).

Programs

Maple

# The function A is defined in A330852.
# Produces the sequence of denominators of the A(n)'s.
seq(denom(A(n)), n = 0 .. 40);