|
|
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.
|
|
9
|
|
|
1, 1, 4, 8, 144, 3456, 172800, 10368000, 3810240000, 177811200000, 9957427200000, 75278149632000000, 1912817782149120000000, 53023308921173606400000000, 17742659631203112173568000000000, 426249654980023566857797632000000000, 9600207854287580784554747166720000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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.
|
|
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
|
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.]
|
|
EXAMPLE
|
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, ...
|
|
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);
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,frac
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|