A330852 Numerator of the rational number A(n) that appears in the formula for the n-th cumulant k(n) = (-1)^n*2^n*(A(n) - (n - 1)!*zeta(n)) of the limiting distribution of the number of comparisons in quicksort, for n >= 2, with A(0) = 1 and A(1) = 0.

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

Offset

0,3

Comments

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 A(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 (-2)^n*A(n), which they denote by a_n. See also Finch (2020).

The Maple program below is based on Tan and Hadjicostas (1993), where the numbers (A(n): n >= 0) are also tabulated.

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

References

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

Links

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

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

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) for s >= 2.]

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.

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.

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.

Example

The first few fractions A(n) are
1, 0, 7/4, 19/8, 937/144, 85981/3456, 21096517/172800, 7527245453/10368000, 19281922400989/3810240000, 7183745930973701/177811200000, ...
The first few fractions (-2)^n*A(n) (= a_n in Hoffman and Kuba and in Finch) are
1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ...

Maple

# Produces the sequence (B(n): n >= 0)
B := proc(m) option remember: local v, g, f, b:
if m = 0 then v := 1: end if: if m = 1 then v := 0: end if:
if 2 <= m then
g := proc(k) add((-1)^a*B(k - a)/(a!*(k - a)!*2^a), a = 0 .. k): end proc:
f := proc(r) add(Stirling1(r + 1, i + 1)*g(r - i), i = 0 .. r): end proc:
b := proc(p) (-1)^p*(add(Stirling1(p + 2, r + 1)*B(p - r)/(p - r)!, r = 1 .. p) + add(f(rr)*f(p - rr), rr = 1 .. p - 1) + 2*(-1)^p*p!*add((-1)^a*B(p - a)/(a!*(p - a)!*2^a), a = 1 .. p) + 2*add(Stirling1(p + 1, i + 1)*g(p - i), i = 1 .. p))/(p - 1): end proc:
v := simplify(b(m)): end if: v: end proc:
# Produces the sequence (A(n): n >= 0)
A := proc(m) option remember: local v:
if m = 0 then v := 1: end if: if m = 1 then v := 0: end if:
if 2 <= m then v := -(m - 1)!*add(A(k + 1)*B(m - 1 - k)/(k!*(m - 1 - k)!), k = 0 .. m - 2) + B(m): end if: v: end proc:
# Produces the sequence of numerators of the A(n)'s
seq(numer(A(n)), n = 0 .. 15);

Mathematica

B[m_] := B[m] = Module[{v, g, f, b}, If[m == 0, v = 1]; If[m == 1, v = 0]; If[2 <= m, g[k_] := Sum[(-1)^a*B[k - a]/(a!*(k - a)!*2^a), {a, 0, k}]; f[r_] := Sum[StirlingS1[r + 1, i + 1]*g[r - i], {i, 0, r}]; b[p_] := (-1)^p*(Sum[StirlingS1[p + 2, r + 1]*B[p - r]/(p - r)!, {r, 1, p}] + Sum[f[rr]*f[p - rr], {rr, 1, p - 1}] + 2*(-1)^p*p!*Sum[(-1)^a*B[p - a]/(a!*(p - a)!*2^a), {a, 1, p}] + 2*Sum[StirlingS1[p + 1, i + 1]*g[p - i], {i, 1, p}])/(p - 1); v = Simplify[b[m]]]; v];
A[m_] := A[m] = Module[{v}, If[ m == 0, v = 1]; If[m == 1, v = 0]; If[2 <= m , v = -(m - 1)!*Sum[A[k + 1]*B[m - 1 - k]/(k!*(m - 1 - k)!), {k , 0 , m - 2}] + B[m]]; v];
Table[Numerator[A[n]], {n, 0, 15}] (* Jean-François Alcover, Aug 17 2020, translated from Maple *)

Crossrefs

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

Sequence in context: A335990 A359636 A330875 * A267237 A057866 A329001

Adjacent sequences: A330849 A330850 A330851 * A330853 A330854 A330855

Keyword

nonn,frac

Author

Petros Hadjicostas, Apr 28 2020

Status

approved