This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A335990 #49 Jul 08 2020 05:10:11
%S A335990 1,0,7,19,565,229621,74250517,30532750703,90558126238639,
%T A335990 37973078754146051,21284764359226368337,1770024989560214080011109,
%U A335990 539780360793818428471498394131,194520883210026428577888559667954807,911287963487139630688627952818633149408727,328394760901508739430228985010652235796369497219
%N 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(-2*t)/(exp(2*gamma*t)*Gamma(1 + 2*t)) 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.
%C A335990 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).
%C A335990 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.
%C A335990 The numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, are given (for p >= 0) by the recurrence.
%C A335990 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 A335990 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.
%C A335990 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 A335990 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.
%C A335990 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.)
%C A335990 The PARI program below is based on a Maple program in Tan and Hadjicostas (1993).
%C A335990 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 A335990 Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991), p. 83.
%H A335990 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 A335990 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 A335990 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 A335990 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. He also evaluates c(2) - c(8), where c(n) = B(n)*(-2)^n.]
%H A335990 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 A335990 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) = (-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).]
%H A335990 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 A335990 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. [He proved that M(t) has a Taylor expansion around t = 0 with an infinite radius of convergence.]
%H A335990 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 pp. 8-11.
%H A335990 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 A335990 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. [The author studies the tail of phi(t) = M(i*t), where i = sqrt(-1).]
%F A335990 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).
%F A335990 Also, B(n) = c(n)/(-2)^n = A329001(n)/A330876(n)/(-2)^n.
%e A335990 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.
%p A335990 For a fast Maple program for the calculation of the numbers (B(n): n >= 0), see A330852.
%o A335990 (PARI) /* Very slow program due to recursion */
%o A335990 g(k) = sum(a=0, k, (-1)^a*B(k - a)/(a!*(k - a)!*2^a));
%o A335990 f(r) = sum(i=0, r, stirling(r + 1, i + 1, 1)*g(r - i));
%o A335990 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);
%o A335990 B(m) = if(m==0, 1, if(m==1, 0, b(m)));
%o A335990 a(n) = numerator(B(n));
%Y A335990 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)).
%K A335990 nonn,frac
%O A335990 0,3
%A A335990 _Petros Hadjicostas_, Jul 03 2020