A330852 - OEIS

%I #71 Aug 17 2020 22:26:01

%S 1,0,7,19,937,85981,21096517,7527245453,19281922400989,

%T 7183745930973701,3616944955616896387,273304346447259998403709,

%U 76372354431694636659849988531,25401366514997931592208126670898607,110490677504100075544188675746430710672527,37160853195949529205295416197788818165029489819

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

%C Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.

%C First he calculates the numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, given for p >= 0 by the recurrence

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

%C Then A(n) = L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.

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

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

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

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

%H Petros Hadjicostas, <a href="/A330852/b330852.txt">Table of n, a(n) for n = 0..30</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 Hennequin's first eight asymptotic cumulants 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 the constants a_s = (-2)^s*A(s) for s >= 2.]

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

%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 study the constants a_s = (-2)^s*A(s) for s >= 2.]

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

%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 p. 10.

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

%e The first few fractions A(n) are

%e 1, 0, 7/4, 19/8, 937/144, 85981/3456, 21096517/172800, 7527245453/10368000, 19281922400989/3810240000, 7183745930973701/177811200000, ...

%e The first few fractions (-2)^n*A(n) (= a_n in Hoffman and Kuba and in Finch) are

%e 1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ...

%p # Produces the sequence (B(n): n >= 0)

%p B := proc(m) option remember: local v, g, f, b:

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

%p if 2 <= m then

%p g := proc(k) add((-1)^a*B(k - a)/(a!*(k - a)!*2^a), a = 0 .. k): end proc:

%p f := proc(r) add(Stirling1(r + 1, i + 1)*g(r - i), i = 0 .. r): end proc:

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

%p v := simplify(b(m)): end if: v: end proc:

%p # Produces the sequence (A(n): n >= 0)

%p A := proc(m) option remember: local v:

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

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

%p # Produces the sequence of numerators of the A(n)'s

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

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

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

%t Table[Numerator[A[n]], {n, 0, 15}] (* _Jean-François Alcover_, Aug 17 2020, translated from Maple *)

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

%K nonn,frac

%O 0,3

%A _Petros Hadjicostas_, Apr 28 2020