|
%I #46 Aug 17 2020 22:27:17
%S 1,1,4,8,144,3456,172800,10368000,3810240000,177811200000,
%T 9957427200000,75278149632000000,1912817782149120000000,
%U 53023308921173606400000000,17742659631203112173568000000000,426249654980023566857797632000000000,9600207854287580784554747166720000000000
%N Denominator 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 given in A330852 is based on Tan and Hadjicostas (1993), where the numbers (A(n): n >= 0) are also tabulated.
%C For a list of references about the theory of the limiting distribution of the number of comparisons in quicksort, which we do not discuss here, see the ones for sequence A330852.
%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="/A330860/b330860.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 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 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.
%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 # The function A is defined in A330852.
%p # Produces the sequence of denominators of the A(n)'s.
%p seq(denom(A(n)), n = 0 .. 40);
%Y Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A330852 (numerators).
%K nonn,frac
%O 0,3
%A _Petros Hadjicostas_, Apr 28 2020
|
