The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A330875 Numerator of the fraction fr(n) that appears in the n-th cumulant k(p) = 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. 5
 1, 0, 7, -19, 937, -85981, 21096517, -7527245453, 19281922400989, -7183745930973701, 3616944955616896387, -273304346447259998403709, 76372354431694636659849988531, -25401366514997931592208126670898607, 110490677504100075544188675746430710672527 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS Hennequin conjectured his cumulant formula in his 1989 paper and proved it in his 1991 thesis. First he calculates the numbers (B(n): n >= 0), with B(0) = 1 and B(0) = 0, given for p >= 0 by the recurrence 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). Then fr(n) = (-2)^n*L_n(B(1),...,B(n)), where L_n(x_1,...,x_n) are the logarithmic polynomials of Bell. 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). 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). 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). REFERENCES Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991), p. 83. LINKS Petros Hadjicostas, Table of n, a(n) for n = 0..30 S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, 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.] Steven Finch, Recursive PGFs for BSTs and DSTs, arXiv:2002.02809 [cs.DS], 2020; see Section 1.4. [He gives the constants a_s = fr(n) for s >= 2.] P. Hennequin, Combinatorial analysis of the quicksort algorithm, Informatique théoretique et applications, 23(3) (1989), 317-333. [He made the first conjectures about fr(n).] M. E. Hoffman and M. Kuba, Logarithmic integrals, zeta values, and tiered binomial coefficients, arXiv:1906.08347 [math.CO], 2019-2020; see Section 5.2. [They study the constants a_s = fr(n) for s >= 2.] Kok Hooi Tan and Petros Hadjicostas, Density and generating functions of a limiting distribution in quicksort, 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. FORMULA a(n) = numerator((-2)^n*A330852(n)/A330860(n)). EXAMPLE The first few fractions fr(n) are 1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ... CROSSREFS Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A329001, A330852, A330860, A330876 (denominators), A330895, A330907. Sequence in context: A191624 A221740 A335990 * A330852 A267237 A057866 Adjacent sequences:  A330872 A330873 A330874 * A330876 A330877 A330878 KEYWORD sign,frac AUTHOR Petros Hadjicostas, Apr 29 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 26 01:49 EDT 2021. Contains 346294 sequences. (Running on oeis4.)