A330876 -id:A330876 - cp's OEIS frontend

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

1, 0, 7, -19, 2260, -229621, 74250517, -30532750703, 90558126238639, -37973078754146051, 21284764359226368337, -1770024989560214080011109, 539780360793818428471498394131, -194520883210026428577888559667954807, 911287963487139630688627952818633149408727

Offset: 0

Petros Hadjicostas, Apr 30 2020

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

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

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

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.

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

# 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);

(* 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 *)

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

A330875 Numerator of the fraction fr(n) that appears in the n-th cumulant k(p) = fr(n) - (-2)^n(n-1)!zeta(n) of the limiting distribution of the number of comparisons in quicksort, for n >= 2, starting with fr(0) = 1 and fr(1) = 0.

Original entry on oeis.org

1, 0, 7, -19, 937, -85981, 21096517, -7527245453, 19281922400989, -7183745930973701, 3616944955616896387, -273304346447259998403709, 76372354431694636659849988531, -25401366514997931592208126670898607, 110490677504100075544188675746430710672527

Offset: 0

Petros Hadjicostas, Apr 29 2020

Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.
First he calculates the numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, 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).
Then fr(n) = (-2)^n*L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.
Hoffman and Kuba (2019, 2020) gave an alternative proof of Hennequin's cumulant formula and gave an alternative calculation for the constants fr(n), which they denote by a_n. See also Finch (2020).
Tan and Hadjicostas (1993) used a Maple program (an update of which can be found in A330852) to tabulate the numbers (fr(n)/(-2)^n: n >= 0).
Sequence A330852 contains additional references that give the theory of the limiting distribution of the number of comparisons in quicksort (and for that reason we omit any discussion of that topic).

			The first few fractions fr(n) are 1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ...

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

Petros Hadjicostas, Table of n, a(n) for n = 0..30
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 Hennequin's first eight asymptotic cumulants can be derived.]
Steven Finch, Recursive PGFs for BSTs and DSTs, arXiv:2002.02809 [cs.DS], 2020; see Section 1.4. [He gives the constants a_s = fr(n) for s >= 2.]
P. Hennequin, Combinatorial analysis of the quicksort algorithm, Informatique théoretique et applications, 23(3) (1989), 317-333. [He made the first conjectures about fr(n).]
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 = fr(n) for s >= 2.]
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 p. 10 for the constants A(n) = fr(n)/(-2)^n.

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

a(n) = numerator((-2)^n*A330852(n)/A330860(n)).

A330895 Numerator of the variance of the random number of comparisons in quicksort applied to lists of length n.

Original entry on oeis.org

0, 0, 0, 2, 29, 46, 3049, 60574, 160599, 182789, 4913659, 1072364, 975570703, 1039388677, 5491155875, 92211937094, 6954047816459, 7225392149719, 2699717387790739, 2785123121790325, 573031978700759, 84009502802237, 45510401082365873, 46518885869845328

Offset: 0

Petros Hadjicostas, May 01 2020

			The variances are: 0, 0, 0, 2/9, 29/36, 46/25, 3049/900, 60574/11025, 160599/19600, 182789/15876, 4913659/317520, 1072364/53361, ... = A330895/A330907.

D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 1973; see answer to Ex. 8(a) of Section 6.2.2.

S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019; see Theorem 2.
V. Iliopoulos, The quicksort algorithm and related topics, arXiv:1503.02504 [cs.DS], 2015.
V. Iliopoulos and D. Penman, Variance of the number of comparisons of randomized quicksort, arXiv:1006.4063 [math.PR], 2010.

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

lista(nn) = {my(va = vector(nn)); for(n=1, nn, va[n] = numerator(n*(7*n+13) - 2*(n+1)*sum(k=1, n, 1/k) - 4*(n+1)^2*sum(k=1, n, 1/k^2))); concat(0,va);}

a(n) = numerator(fr(n)), where fr(n) = n*(7*n + 13) - 2*(n + 1)*Sum_{k=1..n} 1/k - 4*(n + 1)^2*Sum_{k=1..n} 1/k^2.

A330907 Denominator of the variance of the random number of comparisons in quicksort applied to lists of length n.

Original entry on oeis.org

1, 1, 1, 9, 36, 25, 900, 11025, 19600, 15876, 317520, 53361, 38419920, 33127380, 144288144, 2029052025, 129859329600, 115831315600, 37529346254400, 33870234994596, 6144260316480, 799769421360, 387088399938240, 355503061748835, 40953952713465792, 37864231428870000, 316002721554520000, 2056839142975402500, 1612561888092715560000

Offset: 0

Petros Hadjicostas, May 01 2020

			The variances are: 0, 0, 0, 2/9, 29/36, 46/25, 3049/900, 60574/11025, 160599/19600, 182789/15876, 4913659/317520, 1072364/53361, ... = A330895/A330907.

D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 1973; see answer to Ex. 8(a) of Section 6.2.2.

S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019; see Theorem 2.
V. Iliopoulos, The quicksort algorithm and related topics, arXiv:1503.02504 [cs.DS], 2015.
V. Iliopoulos and D. Penman, Variance of the number of comparisons of randomized quicksort, arXiv:1006.4063 [math.PR], 2010.

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

a := n -> denom(2*(n+1)*(harmonic(n,1) + 2*(n+1)*harmonic(n,2))):
seq(a(n), n=0..28); # Peter Luschny, May 02 2020

lista(nn) = {my(va = vector(nn)); for(n=1, nn, va[n] = denominator(n*(7*n+13) - 2*(n+1)*sum(k=1, n, 1/k) - 4*(n+1)^2*sum(k=1, n, 1/k^2))); concat(1, va); }

a(n) = denominator(fr(n)), where fr(n) = n*(7*n + 13) - 2*(n+1)*Sum_{k=1..n} (1/k) - 4*(n+1)^2*Sum_{k=1..n} (1/k^2).

a(n) = denominator(2*(n+1)*(H(n,1) + 2*(n+1)*H(n,2))), where H(n,s) are the generalized harmonic numbers. - Peter Luschny, May 02 2020

A335990 The moment generating function of the limiting distribution of the number of comparisons in quicksort can be written in the form M(t) = m(-2t)/(exp(2gammat)Gamma(1 + 2t)) for |t| < 1/2, where m(z) = Sum_{n >= 0} B(n)z^n/n! for |z| < 1. This sequence gives the numerators of the rational numbers B(n) for n >= 0.

Original entry on oeis.org

1, 0, 7, 19, 565, 229621, 74250517, 30532750703, 90558126238639, 37973078754146051, 21284764359226368337, 1770024989560214080011109, 539780360793818428471498394131, 194520883210026428577888559667954807, 911287963487139630688627952818633149408727, 328394760901508739430228985010652235796369497219

Offset: 0

Petros Hadjicostas, Jul 03 2020

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). (It seems that nu is close to Pi^(1/3) * exp(-1/3 - gamma), but we have no theoretical evidence for that.)
The PARI program below is based on a Maple program in Tan and Hadjicostas (1993).
The rest of the references give the theory of the limiting distribution of the number of comparisons in quicksort (and for that reason we omit any discussion of that topic).

			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.

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

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 Hennequin's first eight asymptotic cumulants 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 the constants a_s = (-2)^s*A(s) for s >= 2. He also evaluates 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 t = 0 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).]

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), A335991 (denominators of B(n)).

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

/* Very slow program due to recursion */
g(k) = sum(a=0, k, (-1)^a*B(k - a)/(a!*(k - a)!*2^a));
f(r) = sum(i=0, r, stirling(r + 1, i + 1, 1)*g(r - i));
b(p) = (-1)^p*(sum(r=1, p, stirling(p + 2, r + 1, 1)*B(p - r)/(p - r)!) + sum(rr=1, p-1, f(rr)*f(p - rr)) + 2*(-1)^p*p!*sum(a=1, p, (-1)^a*B(p - a)/(a!*(p - a)!*2^a)) + 2*sum(i=1, p, stirling(p + 1, i + 1, 1)*g(p - i)))/(p - 1);
B(m) = if(m==0, 1, if(m==1, 0, b(m)));
a(n) = numerator(B(n));

a(n) = numerator(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.

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(-2t)/(exp(2gammat)Gamma(1 + 2t)) 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.

Original entry on oeis.org

1, 1, 4, 8, 36, 3456, 172800, 10368000, 3810240000, 177811200000, 9957427200000, 75278149632000000, 1912817782149120000000, 53023308921173606400000000, 17742659631203112173568000000000, 426249654980023566857797632000000000

Offset: 0

Petros Hadjicostas, Jul 03 2020

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

			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.

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

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

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

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.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A330875 Numerator of the fraction fr(n) that appears in the n-th cumulant k(p) = fr(n) - (-2)^n*(n-1)!*zeta(n) of the limiting distribution of the number of comparisons in quicksort, for n >= 2, starting with fr(0) = 1 and fr(1) = 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A330895 Numerator of the variance of the random number of comparisons in quicksort applied to lists of length n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A330907 Denominator of the variance of the random number of comparisons in quicksort applied to lists of length n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

PARI

Formula

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

PARI

Formula

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A330875 Numerator of the fraction fr(n) that appears in the n-th cumulant k(p) = fr(n) - (-2)^n(n-1)!zeta(n) of the limiting distribution of the number of comparisons in quicksort, for n >= 2, starting with fr(0) = 1 and fr(1) = 0.