|
| |
|
|
A335990
|
|
The moment generating function of the limiting distribution of the number of comparisons in quicksort can be written in the form M(t) = m(-2*t)/(exp(2*gamma*t)*Gamma(1 + 2*t)) for |t| < 1/2, where m(z) = Sum_{n >= 0} B(n)*z^n/n! for |z| < 1. This sequence gives the numerators of the rational numbers B(n) for n >= 0.
|
|
2
|
|
|
|
1, 0, 7, 19, 565, 229621, 74250517, 30532750703, 90558126238639, 37973078754146051, 21284764359226368337, 1770024989560214080011109, 539780360793818428471498394131, 194520883210026428577888559667954807, 911287963487139630688627952818633149408727, 328394760901508739430228985010652235796369497219
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Despite the fact that both the numerator and denominator in the formula M(t) = m(-2*t)/(exp(2*gamma*t)*Gamma(1 + 2*t)) each have a Taylor expansion around t = 0 with a radius of convergence equal to 1/2, the moment generating function M(t) has a Taylor expansion around t = 0 with an infinite radius of convergence. This was proved in Rösler (1991).
The formula for M(t) appears as Theorem 6.1 in Tan and Hadjicostas (1993) and derives from the work of Hennequin (1991). Hennequin conjectured a cumulant formula for the limiting distribution of the number of comparisons in quicksort in his 1989 paper, and he proved it in his 1991 thesis.
The numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, are 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).
The numbers A(n) = L_n(B(1),...,B(n)) = A330852(n)/A330860(n), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell, appear in Hennequin's cumulant formula.
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).
Hoffman and Kuba (2019-2020, Proposition 17) express the constants c(n) = B(n)*(-2)^n = A329001(n)/A330876(n) in terms of "tiered binomial coefficients". In terms of the constants c(n), the moment generating function equals M(t) = Sum_{n >= 0} (c(n)*t^n/n!)/(exp(2*gamma*t)*Gamma(1 + 2*t)) for |t| < 1/2.
Tan and Hadjicostas (1993) proved that lim_{n -> infinity} B(n)/n! = nu, where nu = 0.589164... (approximately). Also, M(-1/2) = nu*exp(gamma), where gamma = A001620 (Euler's constant). (It seems that nu is close to Pi^(1/3) * exp(-1/3 - gamma), but we have no theoretical evidence for that.)
The PARI program below is based on a Maple program in Tan and Hadjicostas (1993).
The rest of the references give the theory of the limiting distribution of the number of comparisons in quicksort (and for that reason we omit any discussion of that topic).
|
|
|
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.]
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. He also evaluates c(2) - c(8), where c(n) = B(n)*(-2)^n.]
Uwe Rösler, A limit theorem for quicksort, Informatique théorique et applications, 25(1) (1991), 85-100. [He proved that M(t) has a Taylor expansion around t = 0 with an infinite radius of convergence.]
|
|
|
FORMULA
|
a(n) = numerator(B(n)), where B(n) = (n-1)!*Sum_{k=0..n-1} A(k+1)*B(n-1-k)/(k!*(n-1-k)!) for n >= 1 with B(0) = 1 and A(n) = A330852(n)/A330860(n).
|
|
|
EXAMPLE
|
The first few fractions are 1/1, 0/1, 7/4, 19/8, 565/36, 229621/3456, 74250517/172800, 30532750703/10368000, 90558126238639/3810240000, ... = A335990/A335991.
|
|
|
MAPLE
|
For a fast Maple program for the calculation of the numbers (B(n): n >= 0), see A330852.
|
|
|
PROG
|
(PARI) /* Very slow program due to recursion */
g(k) = sum(a=0, k, (-1)^a*B(k - a)/(a!*(k - a)!*2^a));
f(r) = sum(i=0, r, stirling(r + 1, i + 1, 1)*g(r - i));
b(p) = (-1)^p*(sum(r=1, p, stirling(p + 2, r + 1, 1)*B(p - r)/(p - r)!) + sum(rr=1, p-1, f(rr)*f(p - rr)) + 2*(-1)^p*p!*sum(a=1, p, (-1)^a*B(p - a)/(a!*(p - a)!*2^a)) + 2*sum(i=1, p, stirling(p + 1, i + 1, 1)*g(p - i)))/(p - 1);
B(m) = if(m==0, 1, if(m==1, 0, b(m)));
a(n) = numerator(B(n));
|
|
|
CROSSREFS
|
Cf. A001620, A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A329001 (numerators of B(n)*(-2)^n), A330852 (numerators of A(n)), A330860 (denominators of A(n)), A330876 (denominators of B(n)*(-2)^n), A335991 (denominators of B(n)).
|
|
|
KEYWORD
|
nonn,frac
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
