A329001 - OEIS

%I #67 Mar 28 2021 12:11:51

%S 1,0,7,-19,2260,-229621,74250517,-30532750703,90558126238639,

%T -37973078754146051,21284764359226368337,-1770024989560214080011109,

%U 539780360793818428471498394131,-194520883210026428577888559667954807,911287963487139630688627952818633149408727

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

%C 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.

%C 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.

%C 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.

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

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

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

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

%H Petros Hadjicostas, <a href="/A329001/b329001.txt">Table of n, a(n) for n = 0..25</a>

%H S. B. Ekhad and D. Zeilberger, <a href="https://arxiv.org/abs/1903.03708">A detailed analysis of quicksort running time</a>, 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.]

%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 a Mathematica program to generate the constants c(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. [He derives some of the asymptotic moments mu(n) whose constant terms are the c(n)'s.]

%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 give a formula for the constants c(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. [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.]

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

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

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

%p # The function A is defined in A330852.

%p # Produces the constants c(n):

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

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

%p 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:

%p v: end proc:

%p # Produces the numerators of c(n):

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

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

%t 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];

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

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

%K sign,frac

%O 0,3

%A _Petros Hadjicostas_, Apr 30 2020