|
%I #32 Dec 22 2021 02:25:32
%S 1,1,4,8,36,3456,172800,10368000,3810240000,177811200000,
%T 9957427200000,75278149632000000,1912817782149120000000,
%U 53023308921173606400000000,17742659631203112173568000000000,426249654980023566857797632000000000
%N 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 denominators of the rational numbers B(n) for n >= 0.
%C 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).
%C 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.
%C The numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, are given (for p >= 0) by the recurrence
%C 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).
%C 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.
%C 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).
%C 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.
%C 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).
%D Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991), p. 83.
%H James A. Fill and Svante Janson, <a href="https://doi.org/10.1007/978-3-0348-8405-1_5">Smoothness and decay properties of the limiting Quicksort density function</a>, In: D. Gardy and A. Mokkadem (eds), Mathematics and Computer Science, Trends in Mathematics, Birkhäuser, Basel, 2000, pp. 53-64.
%H James A. Fill and Svante Janson, <a href="https://doi.org/10.1016/S0196-6774(02)00216-X">Quicksort asymptotics</a>, Journal of Algorithms, 44(1) (2002), 4-28.
%H Steven Finch, <a href="https://arxiv.org/abs/2002.02809">Recursive PGFs for BSTs and DSTs</a>, 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 calculates c(2) - c(8), where c(n) = B(n)*(-2)^n.]
%H P. Hennequin, <a href="http://www.numdam.org/article/ITA_1989__23_3_317_0.pdf">Combinatorial analysis of the quicksort algorithm</a>, Informatique théoretique et applications, 23(3) (1989), 317-333.
%H M. E. Hoffman and M. Kuba, <a href="https://arxiv.org/abs/1906.08347">Logarithmic integrals, zeta values, and tiered binomial coefficients</a>, arXiv:1906.08347 [math.CO], 2019-2020; see Section 5.2. [They study the constants a_s = (-2)^s*A(s) = (-2)^s*L_n(B(1),...,B(s)) = (-2)^s*A330852(s)/A330860(s) for s >= 2. They also study the constants c(n) = B(n)*(-2)^n = A329001(n)/A330876(n).]
%H Mireille Régnier, <a href="http://www.numdam.org/item?id=ITA_1989__23_3_335_0">A limiting distribution for quicksort</a>, Informatique théorique et applications, 23(3) (1989), 335-343.
%H Uwe Rösler, <a href="http://www.numdam.org/item?id=ITA_1991__25_1_85_0">A limit theorem for quicksort</a>, Informatique théorique et applications, 25(1) (1991), 85-100. [He proved that M(t) has a Taylor expansion around zero with an infinite radius of convergence.]
%H Kok Hooi Tan and Petros Hadjicostas, <a href="/A330852/a330852.pdf">Density and generating functions of a limiting distribution in quicksort</a>, Technical Report #568, Department of Statistics, Carnegie Mellon University, Pittsburgh, PA, USA, 1993; see pp. 8-11.
%H Kok Hooi Tan and Petros Hadjicostas, <a href="https://doi.org/10.1016/0167-7152(94)00209-Q">Some properties of a limiting distribution in Quicksort</a>, Statistics and Probability Letters, 25(1) (1995), 87-94.
%H Vytas Zacharovas, <a href="https://arxiv.org/abs/1605.04018">On the exponential decay of the characteristic function of the quicksort distribution</a>, arXiv:1605.04018 [math.CO], 2016. [The author studies the tail of phi(t) = M(i*t), where i = sqrt(-1).]
%F a(n) = denominator(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).
%F Also, B(n) = c(n)/(-2)^n = A329001(n)/A330876(n)/(-2)^n.
%e 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.
%p # For a fast Maple program for the calculation of the numbers (B(n): n >= 0), see A330852.
%Y 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), A335990 (numerators of B(n)).
%K nonn,frac
%O 0,3
%A _Petros Hadjicostas_, Jul 03 2020
|
