cp's OEIS Frontend

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.

%I A330852 #71 Aug 17 2020 22:26:01
%S A330852 1,0,7,19,937,85981,21096517,7527245453,19281922400989,
%T A330852 7183745930973701,3616944955616896387,273304346447259998403709,
%U A330852 76372354431694636659849988531,25401366514997931592208126670898607,110490677504100075544188675746430710672527,37160853195949529205295416197788818165029489819
%N 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.
%C A330852 Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.
%C A330852 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 A330852 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 A330852 Then A(n) = L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.
%C A330852 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 A330852 The Maple program below is based on Tan and Hadjicostas (1993), where the numbers (A(n): n >= 0) are also tabulated.
%C A330852 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 A330852 Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991), p. 83.
%H A330852 Petros Hadjicostas, <a href="/A330852/b330852.txt">Table of n, a(n) for n = 0..30</a>
%H A330852 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 A330852 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 A330852 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 A330852 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 A330852 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 A330852 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 A330852 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 A330852 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 A330852 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 A330852 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 A330852 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 A330852 The first few fractions A(n) are
%e A330852 1, 0, 7/4, 19/8, 937/144, 85981/3456, 21096517/172800, 7527245453/10368000, 19281922400989/3810240000, 7183745930973701/177811200000, ...
%e A330852 The first few fractions (-2)^n*A(n) (= a_n in Hoffman and Kuba and in Finch) are
%e A330852 1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ...
%p A330852 # Produces the sequence (B(n): n >= 0)
%p A330852 B := proc(m) option remember: local v, g, f, b:
%p A330852 if m = 0 then v := 1: end if: if m = 1 then v := 0: end if:
%p A330852 if 2 <= m then
%p A330852 g := proc(k) add((-1)^a*B(k - a)/(a!*(k - a)!*2^a), a = 0 .. k): end proc:
%p A330852 f := proc(r) add(Stirling1(r + 1, i + 1)*g(r - i), i = 0 .. r): end proc:
%p A330852 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 A330852 v := simplify(b(m)): end if: v: end proc:
%p A330852 # Produces the sequence (A(n): n >= 0)
%p A330852 A := proc(m) option remember: local v:
%p A330852 if m = 0 then v := 1: end if: if m = 1 then v := 0: end if:
%p A330852 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 A330852 # Produces the sequence of numerators of the A(n)'s
%p A330852 seq(numer(A(n)), n = 0 .. 15);
%t A330852 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 A330852 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 A330852 Table[Numerator[A[n]], {n, 0, 15}] (* _Jean-François Alcover_, Aug 17 2020, translated from Maple *)
%Y A330852 Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A330860 (denominators).
%K A330852 nonn,frac
%O A330852 0,3
%A A330852 _Petros Hadjicostas_, Apr 28 2020