cp's OEIS Frontend

A330876 Denominator of the fraction fr(n) that appears in the n-th cumulant k(n) = 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.

%I A330876 #34 Jul 08 2020 03:24:39
%S A330876 1,1,1,1,9,108,2700,81000,14883750,347287500,9724050000,
%T A330876 36756909000000,466996528845000000,6472571889791700000000,
%U A330876 1082926002881049327000000000,13008107146607164515924000000000
%N A330876 Denominator of the fraction fr(n) that appears in the n-th cumulant k(n) = 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.
%C A330876 Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis.
%C A330876 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 A330876 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 A330876 Then fr(n) = (-2)^n*L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell.
%C A330876 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).
%C A330876 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).
%C A330876 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).
%D A330876 Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991), p. 83.
%H A330876 Petros Hadjicostas, <a href="/A330876/b330876.txt">Table of n, a(n) for n = 0..30</a>
%H A330876 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 A330876 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 = fr(n) for s >= 2.]
%H A330876 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. [He made the first conjectures about fr(n).]
%H A330876 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 = fr(n) for s >= 2.]
%H A330876 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 for the constants A(n) = fr(n)/(-2)^n.
%F A330876 a(n) = denominator((-2)^n*A330852(n)/A330860(n)).
%e A330876 The first few fractions fr(n) are: 1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ...
%Y A330876 Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A329001, A330852, A330860, A330875 (numerators), A330907, A330895.
%K A330876 nonn,frac
%O A330876 0,5
%A A330876 _Petros Hadjicostas_, Apr 29 2020