A330907 -id:A330907 - 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.

1, 1, 1, 1, 9, 108, 2700, 81000, 14883750, 347287500, 9724050000, 36756909000000, 466996528845000000, 6472571889791700000000, 1082926002881049327000000000, 13008107146607164515924000000000

Offset: 0

Petros Hadjicostas, Apr 29 2020

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).

			The first few fractions fr(n) are: 1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ...

Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991), p. 83.

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.

Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A329001, A330852, A330860, A330875 (numerators), A330907, A330895.

a(n) = denominator((-2)^n*A330852(n)/A330860(n)).

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.

Original entry on oeis.org

1, 0, 7, -19, 937, -85981, 21096517, -7527245453, 19281922400989, -7183745930973701, 3616944955616896387, -273304346447259998403709, 76372354431694636659849988531, -25401366514997931592208126670898607, 110490677504100075544188675746430710672527

Offset: 0

Petros Hadjicostas, Apr 29 2020

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).

			The first few fractions fr(n) are 1, 0, 7, -19, 937/9, -85981/108, 21096517/2700, -7527245453/81000, 19281922400989/14883750, -7183745930973701/347287500, ...

Pascal Hennequin, Analyse en moyenne d'algorithmes, tri rapide et arbres de recherche, Ph.D. Thesis, L'École Polytechnique Palaiseau (1991), p. 83.

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.

Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A329001, A330852, A330860, A330876 (denominators), A330895, A330907.

a(n) = numerator((-2)^n*A330852(n)/A330860(n)).

A330895 Numerator of the variance of the random number of comparisons in quicksort applied to lists of length n.

Original entry on oeis.org

0, 0, 0, 2, 29, 46, 3049, 60574, 160599, 182789, 4913659, 1072364, 975570703, 1039388677, 5491155875, 92211937094, 6954047816459, 7225392149719, 2699717387790739, 2785123121790325, 573031978700759, 84009502802237, 45510401082365873, 46518885869845328

Offset: 0

Petros Hadjicostas, May 01 2020

			The variances are: 0, 0, 0, 2/9, 29/36, 46/25, 3049/900, 60574/11025, 160599/19600, 182789/15876, 4913659/317520, 1072364/53361, ... = A330895/A330907.

D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, 1973; see answer to Ex. 8(a) of Section 6.2.2.

S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019; see Theorem 2.
V. Iliopoulos, The quicksort algorithm and related topics, arXiv:1503.02504 [cs.DS], 2015.
V. Iliopoulos and D. Penman, Variance of the number of comparisons of randomized quicksort, arXiv:1006.4063 [math.PR], 2010.

Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A329001, A330852, A330860, A330875, A330876, A330907 (denominators).

lista(nn) = {my(va = vector(nn)); for(n=1, nn, va[n] = numerator(n*(7*n+13) - 2*(n+1)*sum(k=1, n, 1/k) - 4*(n+1)^2*sum(k=1, n, 1/k^2))); concat(0,va);}

a(n) = numerator(fr(n)), where fr(n) = n*(7*n + 13) - 2*(n + 1)*Sum_{k=1..n} 1/k - 4*(n + 1)^2*Sum_{k=1..n} 1/k^2.

A334935 The product of (n!)^2/8 and the variance of the random number of comparisons needed to sort a list of n distinct items using quicksort.

Original entry on oeis.org

0, 0, 0, 1, 58, 3312, 219528, 17445312, 1665090432, 189515635200, 25472408256000, 4002577182720000, 728259627506688000, 152076300005855232000, 36154290403284480000000, 9714114050265240698880000, 2930311008702414783774720000, 986466808456816565267988480000, 368586443487759607372452986880000

Offset: 0

Petros Hadjicostas, May 16 2020

nonn

S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019; see Theorem 2.
V. Iliopoulos, The quicksort algorithm and related topics, arXiv:1503.02504 [cs.DS], 2015.
V. Iliopoulos and D. Penman, Variance of the number of comparisons of randomized quicksort, arXiv:1006.4063 [math.PR], 2010.

Cf. A330895, A330907.

lista(nn) = {my(va = vector(nn)); for(n=1, nn, va[n] = ((n!)^2/8)*(n*(7*n+13) - 2*(n+1)*sum(k=1, n, 1/k) - 4*(n+1)^2*sum(k=1, n, 1/k^2))); concat(0, va); }

a(n) = ((n!)^2/8)*A330895(n)/A330907(n).

a(n) = ((n!)^2/8)*(n*(7*n + 13) - 2*(n + 1)*Sum_{k=1..n} 1/k - 4*(n + 1)^2*Sum_{k=1..n} 1/k^2).

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A330895 Numerator of the variance of the random number of comparisons in quicksort applied to lists of length n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A334935 The product of (n!)^2/8 and the variance of the random number of comparisons needed to sort a list of n distinct items using quicksort.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

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.

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.