The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A335991 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. 2
1, 1, 4, 8, 36, 3456, 172800, 10368000, 3810240000, 177811200000, 9957427200000, 75278149632000000, 1912817782149120000000, 53023308921173606400000000, 17742659631203112173568000000000, 426249654980023566857797632000000000 (list; graph; refs; listen; history; text; internal format)



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).


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


Table of n, a(n) for n=0..15.

James A. Fill and Svante Janson, Smoothness and decay properties of the limiting Quicksort density function, In: D. Gardy and A. Mokkadem (eds), Mathematics and Computer Science, Trends in Mathematics, Birkhäuser, Basel, 2000, pp. 53-64.

James A. Fill and Svante Janson, Quicksort asymptotics, Journal of Algorithms, 44(1) (2002), 4-28.

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 calculates c(2) - c(8), where c(n) = B(n)*(-2)^n.]

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) = (-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).]

Mireille Régnier, A limiting distribution for quicksort, Informatique théorique et applications, 23(3) (1989), 335-343.

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 zero with an infinite radius of convergence.]

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 pp. 8-11.

Kok Hooi Tan and Petros Hadjicostas, Some properties of a limiting distribution in Quicksort, Statistics and Probability Letters, 25(1) (1995), 87-94.

Vytas Zacharovas, On the exponential decay of the characteristic function of the quicksort distribution, arXiv:1605.04018 [math.CO], 2016. [The author studies the tail of phi(t) = M(i*t), where i = sqrt(-1).]


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).

Also, B(n) = c(n)/(-2)^n = A329001(n)/A330876(n)/(-2)^n.


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.


# For a fast Maple program for the calculation of the numbers (B(n): n >= 0), see A330852.


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)).

Sequence in context: A229535 A309618 A047710 * A063580 A003049 A098563

Adjacent sequences: A335988 A335989 A335990 * A335992 A335993 A335994




Petros Hadjicostas, Jul 03 2020



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 23 19:17 EDT 2023. Contains 361449 sequences. (Running on oeis4.)