login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A329001 Numerator of the rational constant term c(n) of the n-th moment mu(n) of the limiting distribution of the number of comparisons in quicksort (for n >= 0). 7
1, 0, 7, -19, 2260, -229621, 74250517, -30532750703, 90558126238639, -37973078754146051, 21284764359226368337, -1770024989560214080011109, 539780360793818428471498394131, -194520883210026428577888559667954807, 911287963487139630688627952818633149408727 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Let X_n be the number of comparisons needed to sort a list of n distinct numbers by quicksort. Then E(X_n) = A115107(n)/A096620(n) = -4*n + + 2*(1+n)*HarmonicNumber(n) or E(X_n) = A093418(n)/A096620(n) = -3*n + + 2*(1+n)*HarmonicNumber(n) depending on the assumptions.

Régnier (1989) and Rösler (1991) proved that (X_n - E(X_n))/n converges a.s. (and in other modes of convergence) to a non-degenerate r.v. X. Rösler proved the existence of all moments for X and Tan and Hadjicostas (1995) proved that it has a density w.r.t. to the Lebesgue measure. Fill and Janson (2000, 2002) proved many other properties of the distribution of X.

Hennequin (1989, 1991) calculated moments and cumulants of X. He proved that mu(n) = E(X^n) is a linear combination of a finite number of zeta values at positive integer arguments with rational coefficients plus a rational constant c(n). It is the numerators of this constant term c(n) of mu(n) that we tabulate here, while the denominators are in A330876.

Hennequin (1991) proved that the n-th cumulant of X for n >= 2 is k(n) = (-2)^n*(A(n) - (n-1)!*zeta(n)), where A(n) = A330852(n)/A330860(n) with A(0) = 1 and A(1) = 0. Also, (-2)^n*A(n) = A330875(n)/A330876(n); see Hoffman and Kuba (2019-2020) and Finch (2020).

Actually, Hoffman and Kuba (2019-2020, Proposition 17) express the constants c(n) in terms of "tiered binomial coefficients". Finch (2020) uses their results to write a Mathematica program with which he calculates at least c(2) - c(8). The values c(2) - c(8) have also been calculated indirectly by Ekhad and Zeilberger (2019).

Because moments and cumulants are connected via the relationship mu(n) = Sum_{s=0..n-1} binomial(n-1,s)*k(s+1)*mu(n-1-s) (e.g., see Tan and Hadjicostas (1993)), we easily deduce that c(n) = Sum_{s=0..n-1} binomial(n-1,s)*(-2)^(s+1)*A(s+1)*c(n-1-s) for n >= 1 because c(1) = A(1) = mu(1) = k(1) = 0 and k(n) = (-2)^n*A(n) - (-2)^n*(n-1)!*zeta(n) for n >= 2 and c(n) is the constant term of mu(n).

REFERENCES

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

LINKS

Petros Hadjicostas, Table of n, a(n) for n = 0..25

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 the first eight asymptotic moments mu(n) can be derived.]

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 a Mathematica program to generate the constants c(n).]

P. Hennequin, Combinatorial analysis of the quicksort algorithm, Informatique théoretique et applications, 23(3) (1989), 317-333. [He derives some of the asymptotic moments mu(n) whose constant terms are the c(n)'s.]

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 give a formula for the constants c(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. [In Section 5, he gives a recursion for the moments mu(n), which potentially can be used to find the constants c(n), but he does not do any explicit calculations.]

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

FORMULA

Recurrence for the fractions: c(n) = Sum_{s=0..n-1} binomial(n-1,s)*(-2)^(s+1)*A(s+1)*c(n-1-s) for n >= 1, with c(0) = 1 = A(0) and c(1) = 0 = A(1), where A(n) = A330852(n)/A330860(n) and (-2)^n*A(n) = A330875(n)/A330876(n).

EXAMPLE

The first few c(n) are {1, 0, 7, -19, 2260/9, -229621/108, 74250517/2700, -30532750703/81000, 90558126238639/14883750, -37973078754146051/347287500, ...}.

MAPLE

# The function A is defined in A330852.

# Produces the constants c(n):

c := proc(p) local v, a: option remember:

if p = 0 then v := 1; end if: if p = 1 then v := 0: end if:

if 2 <= p then v := (p - 1)!*add((-2)^(a + 1)*A(a + 1)*c(p - 1 - a)/(a!*(p - 1 - a)!), a = 0 .. p - 1): end if:

v: end proc:

# Produces the numerators of c(n):

seq(numer(c(n)), n=0..15);

MATHEMATICA

(* The function A is defined in A330852. *)

c[p_] := c[p] = Module[{v, a}, If[p == 0, v = 1; ]; If[p == 1, v = 0]; If[2 <= p, v = (p - 1)!*Sum[(-2)^(a + 1)*A[a + 1]*c[p - 1 - a]/(a!*(p - 1 - a)!), {a, 0, p - 1}]]; v];

Table[Numerator[c[n]], {n, 0, 15}] (* Jean-François Alcover, Mar 28 2021, after Maple code *)

CROSSREFS

Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A330852, A330860, A330875, A330876 (denominators).

Sequence in context: A330852 A267237 A057866 * A334982 A339698 A301808

Adjacent sequences:  A328998 A328999 A329000 * A329002 A329003 A329004

KEYWORD

sign,frac

AUTHOR

Petros Hadjicostas, Apr 30 2020

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 25 23:39 EDT 2021. Contains 346294 sequences. (Running on oeis4.)