# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/ Search: id:a329001 Showing 1-1 of 1 %I A329001 #67 Mar 28 2021 12:11:51 %S A329001 1,0,7,-19,2260,-229621,74250517,-30532750703,90558126238639, %T A329001 -37973078754146051,21284764359226368337,-1770024989560214080011109, %U A329001 539780360793818428471498394131,-194520883210026428577888559667954807,911287963487139630688627952818633149408727 %N 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). %C A329001 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 A329001 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 A329001 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 A329001 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 A329001 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 A329001 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 A329001 Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991). %H A329001 Petros Hadjicostas, Table of n, a(n) for n = 0..25 %H A329001 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.] %H A329001 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. %H A329001 James A. Fill and Svante Janson, Quicksort asymptotics, Journal of Algorithms, 44(1) (2002), 4-28. %H A329001 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).] %H A329001 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.] %H A329001 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).] %H A329001 Mireille Régnier, A limiting distribution for quicksort, Informatique théorique et applications, 23(3) (1989), 335-343. %H A329001 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.] %H A329001 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. %H A329001 Kok Hooi Tan and Petros Hadjicostas, Some properties of a limiting distribution in Quicksort, Statistics and Probability Letters, 25(1) (1995), 87-94. %H A329001 Vytas Zacharovas, On the exponential decay of the characteristic function of the quicksort distribution, arXiv:1605.04018 [math.CO], 2016. %F A329001 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 A329001 The first few c(n) are {1, 0, 7, -19, 2260/9, -229621/108, 74250517/2700, -30532750703/81000, 90558126238639/14883750, -37973078754146051/347287500, ...}. %p A329001 # The function A is defined in A330852. %p A329001 # Produces the constants c(n): %p A329001 c := proc(p) local v, a: option remember: %p A329001 if p = 0 then v := 1; end if: if p = 1 then v := 0: end if: %p A329001 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 A329001 v: end proc: %p A329001 # Produces the numerators of c(n): %p A329001 seq(numer(c(n)), n=0..15); %t A329001 (* The function A is defined in A330852. *) %t A329001 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 A329001 Table[Numerator[c[n]], {n, 0, 15}] (* _Jean-François Alcover_, Mar 28 2021, after Maple code *) %Y A329001 Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A330852, A330860, A330875, A330876 (denominators). %K A329001 sign,frac %O A329001 0,3 %A A329001 _Petros Hadjicostas_, Apr 30 2020 # Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE