A288964 -id:A288964 - cp's OEIS frontend

A093418 Numerator of -3n + 2(1+n)*HarmonicNumber(n).

0, 1, 3, 17, 53, 62, 163, 717, 3489, 3727, 43391, 45596, 619313, 644063, 667229, 2756003, 24124223, 24784883, 160941559, 164719333, 33664415, 11451017, 268428987, 819836496, 20845424563, 21181779967, 193553388003, 196368607553, 5773568883787, 5849866645327

Offset: 0

Amarnath Murthy, Mar 30 2004

Numerator of the average time to quicksort n items in random order.
From Petros Hadjicostas, Oct 20 2019: (Start)
Depending on the assumptions used in the literature, the average number to sort n items in random order by quicksort appears as -C*n + 2*(1+n)*HarmonicNumber(n), where C = 2, 3, or 4. See, for example, A115107 and A288964. Other variations of the above formula are possible.
Let X_n be the random number of comparisons needed to sort a list of numbers in the symmetric group S_n and let R_n be the rank of the pivot. According to Havil (2003, pp. 128-130), we have X_n = n + X_{R_n-1} + X_{n-R_n} because it takes 1 unit of comparison time to pick the pivot and n-1 comparisons to divide the data into two lists of numbers (less than the pivot and greater than the pivot). No matter how we pick the pivot, we have to assume that R_n is jointly independent of (X_1, ..., X_n). We let X_0 = 0.
Denoting expectation by E(.) and conditional expectation by E(.|.), we have E(X_n) = Sum_{r = 1..n} E(n + X_{R_n-1} + X_{n-R_n} | R_n=r) * P(R_n=r) = n + (1/n) * (E(X_{r-1}) + E(X_{n-r})) The last step follows from the assumed independence of R_n from (X_1, ..., X_n). This simplifies to E(X_n) = n + (2/n) * Sum_{r = 0..n-1} E(X_r). As in Havil (2003), solving the recurrence we get E(X_n) = fr(n) = -3*n + 2*(1+n)*HarmonicNumber(n). Here a(n) = numerator(E(X_n)) and A096620(n) = denominator(E(X_n)).
Note that E(X_n)*n! = (-3*n + 2*(1+n)*HarmonicNumber(n)) * n! = A063090(n), and according to the documentation of that sequence, A063090(n)/(n*n!) is the "average number of comparisons needed to find a node in a binary search tree containing n nodes inserted in a random order". See Knuth (1998, Vol. 3, pp. 430-431 and Exercise 6 on pp. 454-455).
Other authors (e.g., Cameron (1996)) do not count the choice of the pivot as a comparison time. In such a case, if we let Y_n be the modified number of comparisons used by quicksort to sort a random list of length n, we get the modified recurrence Y_n = n - 1 + Y_{R_n-1} + Y_{n-R_n}, from which we get E(Y_n) = n - 1 +  (2/n) * Sum_{r = 0..n-1} E(Y_r). Solving this modified recurrence, we get E(Y_n) = -4*n + + 2*(1+n)*HarmonicNumber(n). In such a case, A115107(n) = numerator(E(Y_n)) = numerator(-4*n + 2*(1+n)*HarmonicNumber(n)) and A288964(n) = n! * E(Y_n) = n! * (-4*n + 2*(1+n)*HarmonicNumber(n)).
(End)

			fr(n) = 0, 1, 3, 17/3, 53/6, 62/5, 163/10, 717/35, 3489/140, ... = A093418/A096620.

Peter J. Cameron, Combinatorics: Topics, Techniques and Algorithms, Cambridge Univ. Press, 1996; see pp. 66-68.
J. H. Conway and R. K. Guy, The Book of Numbers. New York: Springer-Verlag, 1996, pp. 143 and 258-259.
Julian Havil, Gamma: Exploring Euler's constant, Princeton University Press, 2003; see pp. 128-130.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, 1998; see pp. 427-431 and 454-455.

G. C. Greubel, Table of n, a(n) for n = 0..1000 [recomputed for offset 0 by _Georg Fischer_, Oct 13 2019]
S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019. [They have the recurrence with n-1, rather than n, from which they get -4*n + 2*(1+n)*HarmonicNumber(n) for the average number of comparisons.]
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer, 2011; see p. 4. [They agree with Cameron's recurrence and the numerators are in A115107.]
Eric Weisstein's World of Mathematics, Quicksort. [He uses Havil's recurrence.]
Eric Weisstein's World of Mathematics, Harmonic Number.
Wikipedia, Quicksort. [Uses Cameron's recurrence and the numerators are in A115107.]

Cf. A001008, A002805, A063090, A096620, A115107, A288964.

The denominators in A096620 are essentially the same as the numbers in A093419, which are the denominators of A093412.

[Numerator(2*(n+1)*HarmonicNumber(n) -3*n): n in [0..50]]; // G. C. Greubel, Sep 01 2018

a := n -> numer(2*(n + 1)*(Psi(n + 1) + gamma) - 3*n);
seq(a(n), n=0..26); # Peter Luschny, Aug 26 2019

Numerator[Table[2*Sum[Sum[1/i, {i, 1, k}], {k, 1, n}]-n, {n, 0, 20}]] (* or *) Numerator[Table[2*Sum[HarmonicNumber[k], {k, 1, n}]-n, {n, 0, 20}]]
Numerator[Table[2*(n+1)*HarmonicNumber[n] - 3*n, {n, 0, 50}]] (* G. C. Greubel, Sep 01 2018 *)

{h(n) = sum(k=1,n,1/k)};
for(n=0,50, print1(numerator(2*(n+1)*h(n) -3*n), ", ")) \\ G. C. Greubel, Sep 01 2018

from fractions import Fraction
from itertools import count, islice
def agen(): # generator of terms
    Hn = Fraction(0, 1)
    for n in count(0):
        yield (-3*n + 2*(1+n)*Hn).numerator
        Hn += Fraction(1, n+1)
print(list(islice(agen(), 27))) # Michael S. Branicky, Apr 17 2022

G.f. for fractions fr(n): -(x+2*log(1-x))/(1-x)^2. - Vladeta Jovovic, Jul 05 2004
a(n) = 1 + (1/n!) * Sum_{k=0..n} (-1)^(n-k) * Stirling1(n, k) * (k-1) * 2^k. - Vladeta Jovovic, Jul 05 2004
a(n) = numerator(-n + 2 * H^{2}(n)), where H^{2}(n) = Sum_{k=1..n} HarmonicNumber(k) is second-order harmonic number. - Alexander Adamchuk, Nov 01 2004

Edited by Eric W. Weisstein, Jul 01 2004

Offset changed to 0 by Petros Hadjicostas, Aug 26 2019

A096620 Denominator of -3n + 2(1+n)*HarmonicNumber(n).

Original entry on oeis.org

1, 1, 1, 3, 6, 5, 10, 35, 140, 126, 1260, 1155, 13860, 12870, 12012, 45045, 360360, 340340, 2042040, 1939938, 369512, 117572, 2586584, 7436429, 178474296, 171609900, 1487285800, 1434168450, 40156716600, 38818159380, 1164544781400, 4512611027925, 2187932619600

Offset: 0

Eric W. Weisstein, Jul 01 2004

Also, with initial term 0 (really this is A093419), denominator of q_n = -4*n + 2*(1+n)*HarmonicNumber(n) (Cameron). Cf. A115107.
Average time to quicksort n items in random order.
From Petros Hadjicostas, Oct 25 2019: (Start)
Depending on the assumptions used in the literature, the average number to sort n items in random order by quicksort appears as -C*n + 2*(1+n)*HarmonicNumber(n), where C = 2, 3, or 4. See, for example, A115107 and A288964. Other variations of the above formula are possible.
Let X_n be the random number of comparisons needed to sort a list of numbers in the symmetric group S_n and let R_n be the rank of the pivot. According to Havil (2003, pp. 128-130), we have X_n = n + X_{R_n-1} + X_{n-R_n} because it takes 1 unit of comparison time to pick the pivot and n-1 comparisons to divide the data into two lists of numbers (less than the pivot and greater than the pivot). No matter how we pick the pivot, we have to assume R_n is jointly independent of (X_1, ..., X_n). We let X_0 = 0.
Denoting expectation by E(.) and conditional expectation by E(.|.), we have E(X_n) = Sum_{r = 1..n} E(n + X_{R_n-1} + X_{n-R_n} | R_n=r) * P(R_n=r) = n + (1/n) * (E(X_{r-1}) + E(X_{n-r})) The last step follows from the assumed independence of R_n from (X_1, ..., X_n). This simplifies to E(X_n) = n + (2/n) * Sum_{r = 0..n-1} E(X_r). As in Havil (2003), solving the recurrence we get E(X_n) = fr_1(n) = -3*n + 2*(1+n)*HarmonicNumber(n). Here A093418(n) = numerator(E(X_n)) = numerator(fr_1(n)) and a(n) = denominator(E(X_n)) = denominator(fr_1(n)).
Note that E(X_n)*n! = (-3*n + 2*(1+n)*HarmonicNumber(n)) * n! = A063090(n), and according to the documentation of that sequence, A063090(n)/(n*n!) is the "average number of comparisons needed to find a node in a binary search tree containing n nodes inserted in a random order". See Knuth (1998, Vol. 3, pp. 430-431 and Exercise 6 on pp. 454-455).
Other authors (e.g., Cameron (1996)) do not count the choice of the pivot as a comparison time. In such a case, if we let Y_n be the modified number of comparisons used by quicksort to sort a random list of length n, we get the modified recurrence Y_n = n - 1 + Y_{R_n-1} + Y_{n-R_n}, from which we get E(Y_n) = n - 1 +  (2/n) * Sum_{r = 0..n-1} E(Y_r). Solving this modified recurrence, we get E(Y_n) = fr_2(n) = -4*n + + 2*(1+n)*HarmonicNumber(n). In such a case, A115107(n) = numerator(E(Y_n)) = numerator(-4*n + 2*(1+n)*HarmonicNumber(n)) and A288964(n) = n! * E(Y_n) = n! * (-4*n + 2*(1+n)*HarmonicNumber(n)). In addition, a(n) = denominator(E(Y_n)) = denominator(fr_2(n)).
(End)

			Extended by _Petros Hadjicostas_, Oct 25 2019: (Start)
fr_1(n) = 0, 1, 3, 17/3, 53/6, 62/5, 163/10, 717/35, 3489/140, ... = -3*n + 2*(1+n)*HarmonicNumber(n) = A093418(n)/a(n) = A288964(n)/n! + n (Havil's recurrence, which is related to Knuth's recurrence--see comments above).
fr_2(n) = 0, 0, 1, 8/3, 29/6, 37/5, 103/10, 472/35, 2369/140, ... = -4*n + 2*(1+n)*HarmonicNumber(n) = A115107(n)/a(n) = A288964/n! (Cameron's recurrence, which is the same as Kauers and Paule's recurrence--see comments above).
Both fr_1(n) and fr_2(n) are equal to the average time to quicksort n items in random order but under slightly different assumptions.
(End)

Peter J. Cameron, Combinatorics: Topics, Techniques and Algorithms, Cambridge Univ. Press, 1996; see pp. 66-68.
J. H. Conway and R. K. Guy, The Book of Numbers. New York: Springer-Verlag, 1996, pp. 143 and 258-259.
Julian Havil, Gamma: Exploring Euler's constant, Princeton University Press, 2003; see pp. 128-130.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, 1998; see pp. 427-431 and 454-455.

G. C. Greubel, Table of n, a(n) for n = 0..1000
S. B. Ekhad and D. Zeilberger, A detailed analysis of quicksort running time, arXiv:1903.03708 [math.PR], 2019. [They have the recurrence with n-1, rather than n, from which they get -4*n + 2*(1+n)*HarmonicNumber(n) for the average number of comparisons.]
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer, 2011; see p. 4. [They agree with Cameron's recurrence that yields numerators in A115107 and denominators in this sequence.]
Eric Weisstein's World of Mathematics, Quicksort. [He uses Havil's recurrence which yields numerators in sequence A093418 and denominators in this sequence.]
Eric Weisstein's World of Mathematics, Harmonic Number.
Wikipedia, Quicksort. [The article uses Cameron's recurrence which yields numerators in A115107 and denominators in this sequence.]

Cf. A063090, A093418 (one set of numerators), A115107 (another set of numerators), A288964.

Essentially the same as A093419.

[Denominator(2*(n+1)*HarmonicNumber(n+1) -1): n in [0..50]]; // G. C. Greubel, Sep 01 2018

Denominator[Table[2*(n + 1)*HarmonicNumber[n + 1] - 1, {n, 0, 50}]] (* G. C. Greubel, Sep 01 2018 *)

{h(n) = sum(k=1,n,1/k)};
for(n=0,50, print1(denominator(2*(n+1)*h(n+1) -1), ", ")) \\ G. C. Greubel, Sep 01 2018

from fractions import Fraction
from itertools import count, islice
def agen(): # generator of terms
    Hn = Fraction(0, 1)
    for n in count(0):
        yield (-3*n + 2*(1+n)*Hn).denominator
        Hn += Fraction(1, n+1)
print(list(islice(agen(), 30))) # Michael S. Branicky, Apr 17 2022

a(n) = Denominator(2*(n+1)*HarmonicNumber(n+1)-1). - Gary Detlefs, Sep 14 2011
a(n) = Denominator((H(n+1) + H(n))/(H(n+1) - H(n))), where H(n) is the n-th harmonic number. - Gary Detlefs, Oct 03 2011
From Petros Hadjicostas, Oct 25 2019: (Start)
G.f. for fr_1(n) = E(X_n): -(x + 2*log(1-x))/(1-x)^2 (due to Vladeta Jovovic, Jul 05 2004).
G.f. for fr_2(n) = E(Y_n): -2*(x + log(1-x))/(1-x)^2 (Cameron (1996), p. 68). (End)

Offset corrected by Gary Detlefs, Sep 14 2011

A063090 a(n)/(n*n!) is the average number of comparisons needed to find a node in a binary search tree containing n nodes inserted in a random order.

Original entry on oeis.org

1, 6, 34, 212, 1488, 11736, 103248, 1004832, 10733760, 124966080, 1575797760, 21403457280, 311623441920, 4842481190400, 80007869491200, 1400671686758400, 25902542427955200, 504597366114508800, 10328835149402112000

Offset: 1

Rob Arthan, Aug 06 2001

a(n) is the sum over all permutations, p, of {1, ..., n} of the number of comparisons required to find all the entries in the tree formed when the order of insertion is p(1), p(2), ... p(n). To derive the formula given, first group the trees according to the value of k = p(1). For a given k, p determines a permutation of {1, ..., k-1} that gives the structure of the left subtree. By symmetry, the contribution of the right subtrees will be the same as the left subtrees. Now count and simplify.

a(n) mod n is n-2 or 0 depending on whether n is prime or not. - Gary Detlefs, May 28 2012

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, p. 427, C(n).

T. D. Noe, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Quicksort.

Cf. A000108, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971.

[Factorial(n)*((2*n+2)*HarmonicNumber(n) - 3*n): n in [1..30]]; // G. C. Greubel, Sep 01 2018

A[1]:= 1:
for n from 2 to 30 do A[n]:= (2*n-1)*(n-1)!+(n+1)*A[n-1] od:
seq(A[n],n=1..30); # Robert Israel, Sep 21 2014

a[n_] := n!*((2*n+2)*HarmonicNumber[n] - 3*n); Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Sep 20 2012, after Gary Detlefs *)

{h(n) = sum(k=1,n, 1/k)};
for(n=1,30, print1(n!*(2*(n+1)*h(n) - 3*n), ", ")) \\ G. C. Greubel, Sep 01 2018

a(1) = 1, a(n) = n*n! + 2 * Sum_{k=1}^{n-1} (n-1)!/k! * a(k).
a(n) = (2*n - 1)*(n - 1)! + (n + 1)*a(n-1).
E.g.f.: -(x+2*log(1-x))/(1-x)^2. - Vladeta Jovovic, Sep 15 2003
a(n) = Sum_{k=0..n} |Stirling1(n, k)|*A000337(k). - Vladeta Jovovic, Jul 06 2004
a(n) = 2*(n+1)*abs(Stirling1(n+1, 2))-3*n*n!. - Vladeta Jovovic, Jul 06 2004
a(n) = n!*((2*n+2)*h(n) - 3*n), where h(n) is the n-th harmonic number. - Gary Detlefs, May 28 2012
a(n) = A288964(n) + n!*n (because this sequence and A288964 have the same definition related to quicksort but under slightly different assumptions). - Petros Hadjicostas, May 03 2020

More terms from Vladeta Jovovic, Aug 08 2001

Missing brackets in the formula in the name inserted by Rob Arthan, Sep 21 2014

A115107 Numerator of q_n = -4n + 2(1+n)*HarmonicNumber(n).

Original entry on oeis.org

0, 0, 1, 8, 29, 37, 103, 472, 2369, 2593, 30791, 32891, 452993, 476753, 499061, 2080328, 18358463, 18999103, 124184839, 127860511, 26274175, 8982005, 211524139, 648798629, 16562041459, 16891532467, 154883957203, 157646059403, 4649180818987, 4724140023307

Offset: 0

N. J. A. Sloane, Mar 07 2006

Average time to quicksort n items in random order.
From Petros Hadjicostas, Oct 26 2019: (Start)
Depending on the assumptions used in the literature, the average number to sort n items in random order by quicksort appears as -C*n + 2*(1+n)*HarmonicNumber(n), where C = 2, 3, or 4. See, for example, A093418 and A288964. Other variations of the above formula are possible.
Let X_n be the random number of comparisons needed to sort a list of numbers in the symmetric group S_n and let R_n be the rank of the pivot. According to Havil (2003, pp. 128-130), we have X_n = n + X_{R_n-1} + X_{n-R_n} because it takes 1 unit of comparison time to pick the pivot and n-1 comparisons to divide the data into two lists of numbers (less than the pivot and greater than the pivot). No matter how we pick the pivot, we have to assume X_n and R_n are independent random variables. We let X_0 = 0.
Denoting expectation by E(.) and conditional expectation by E(.|.), we have E(X_n) = Sum_{r = 1..n} E(n + X_{R_n-1} + X_{n-R_n} | R_n=r) * P(R_n=r) = n + (1/n) * (E(X_{r-1}) + E(X_{n-r})) The last step follows from the assumed independence of X_n and R_n. This simplifies to E(X_n) = n + (2/n) * Sum_{r = 0..n-1} E(X_r). As in Havil (2003), solving the recurrence we get E(X_n) = -3*n + 2*(1+n)*HarmonicNumber(n). Here A093418(n) = numerator(E(X_n)) and A096620(n) = denominator(E(X_n)).
Note that E(X_n)*n! = (-3*n + 2*(1+n)*HarmonicNumber(n)) * n! = A063090(n), and according to the documentation of that sequence, A063090(n)/(n*n!) is the "average number of comparisons needed to find a node in a binary search tree containing n nodes inserted in a random order". See Knuth (1998, Vol. 3, pp. 430-431 and Exercise 6 on pp. 454-455).
Other authors (e.g., Cameron (1996)) do not count the choice of the pivot as a comparison time. In such a case, if we let Y_n be the modified number of comparisons used by quicksort to sort a random list of length n, we get the modified recurrence Y_n = n - 1 + Y_{R_n-1} + Y_{n-R_n}, from which we get E(Y_n) = n - 1 +  (2/n) * Sum_{r = 0..n-1} E(Y_r). Solving this modified recurrence, we get E(Y_n) = fr_2(n) = -4*n + + 2*(1+n)*HarmonicNumber(n). In such a case, a(n) = numerator(E(Y_n)) = numerator(fr(n)) and A288964(n) = n! * E(Y_n) = n! * fr(n). In addition, A096620(n) = denominator(E(Y_n)) = denominator(fr(n)). (End)
From Peter Bala, Jul 16 2025: (Start)
Define b(n) = numerator( Sum_{k >= 1} 1/((k + 1)*(k + 3*n - 1)*(k + 3*n)) ).
Define c(n) = numerator( Sum_{k >= 1} 1/((k + 1)*(k + 3*n - 2)*(k + 3*n - 1)) ).
Define d(n) = numerator( Sum_{k >= 1} 1/((k + 1)*(k + 3*n - 3)*(k + 3*n - 2)) ).
Then it appears that a(3*n-1) and b(n) are frequently equal, a(3*n-2) and c(n) are frequently equal and a(3*n-3) and d(n) are frequently equal. See the Example section below. (End)

			q_n = fr(n) = 0, 0, 1, 8/3, 29/6, 37/5, 103/10, 472/35, 2369/140, 2593/126, ... = a(n)/A096620(n) = A288964(n)/n!.
From _Petros Hadjicostas_, Oct 26 2019: (Start)
Using the notation in the comments, Y_3 = 3-1 + Y_{R_3-1} + Y_{3-R_3} = 2 + Y_{R_3-1} + Y_{3-R_3}, where the (random) pivot R_3 has a uniform distribution on the set {1,2,3} (and it is independent of Y_1, Y_2, Y_3).
Since P(R_3 = r) = 1/3 for r = 1,2,3, we have that Y_3 = 2 + Y_0 + Y_2 = 2 + 0 + 1 = 3 w.p. 1/3; Y_3 = 2 + Y_1 + Y_1 = 2 w.p. 1/3; and Y_3 = 2 + Y_2 + Y_0 = 2 + 1 + 0 = 3 w.p. 1/3. Thus, fr(3) = E(Y_n) = 3*(1/3) + 2*(1/3) + 3*(1/3) = 8/3, and a(3) = numerator(8/3) = 8 while A096620(3) = 3. (End)
From _Peter Bala_, Jul 16 2025: (Start)
b(n), c(n) and d(n) are defined in the Comments section.
a(3*n-1)/b(n) for 1 <= n <= 100:
[1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 1, 1, 1, 19, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 17, 1, 31, 1, 19, 1, 1, 1, 1, 1].
a(3*n-2)/c(n) for 1 <= n <= 100:
[0, 1, 8, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 17, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23].
a(3*n-3)/d(n) for 1 <= n <= 100:
[0, 8, 1, 1, 1, 8, 1, 5, 1, 7, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 17, 1, 1, 1, 1, 1, 1, 1, 1]. (End)

Peter J. Cameron, Combinatorics: Topics, Techniques and Algorithms, Cambridge Univ. Press, 1996; see pp. 66-68.
J. H. Conway and R. K. Guy, The Book of Numbers. New York: Springer-Verlag, 1996, pp. 143 and 258-259.
Julian Havil, Gamma: Exploring Euler's constant, Princeton University Press, 2003; see pp. 128-130.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, 1998; see pp. 427-431 and 454-455.

G. C. Greubel, Table of n, a(n) for n = 0..1000 [a(0) = 0 by _Georg Fischer_, Oct 28 2019]
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer, 2011; see p. 4. [They agree with Cameron's recurrence that yields numerators in this sequence and denominators in A096620.]
Eric Weisstein's World of Mathematics, Quicksort. [He uses Havil's recurrence which yields numerators in A093418 and denominators in A096620.]
Eric Weisstein's World of Mathematics, Harmonic Number.
Wikipedia, Quicksort. [The article uses Cameron's recurrence which yields numerators in this sequence and denominators in A096620.]

Cf. A063090, A093418, A096620 (denominators), A288964.

[Numerator(-4*n + 2*(n+1)*HarmonicNumber(n)): n in [1..30]]; // G. C. Greubel, Sep 01 2018

a[n_] := Numerator[ -4n + 2(n + 1)HarmonicNumber[n]]; Array[a, 29] (* Robert G. Wilson v, May 01 2006 *)

{h(n) = sum(k=1,n,1/k)};
for(n=1,30, print1(numerator(-4*n + 2*(n+1)*h(n)), ", ")) \\ G. C. Greubel, Sep 01 2018

from sympy import harmonic
def A115107(n): return ((n+1<<1)*harmonic(n)-(n<<2)).p # Chai Wah Wu, Feb 04 2024

a(0) = 0 prepended by Petros Hadjicostas, Oct 26 2019

A288965 Number of key comparisons to sort all n! permutations of n elements by the optimal dual-pivot quicksort.

Original entry on oeis.org

0, 0, 2, 16, 114, 866, 7188, 65580, 655872, 7157376, 84775680, 1084343040, 14906039040, 219267751680, 3437854963200, 57247256424960, 1009189972869120, 18779054120386560, 367876307230064640, 7568437652936294400, 163164173556503347200, 3678547646214424166400

Offset: 0

Daniel Krenn, Jun 20 2017

nonn

Daniel Krenn, Table of n, a(n) for n = 0..100
M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths, arXiv:1611.00258 [math.CO], 2016.
M. Aumüller, M. Dietzfelbinger, C. Heuberger, D. Krenn, and H. Prodinger, Dual-Pivot Quicksort: Optimality, Analysis and Zeros of Associated Lattice Paths, Combin. Probab. Comput. 28(4) (2019), 485-518.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
R. Neininger and J. Straub, Probabilistic analysis of the dual-pivot quicksort "count", arXiv:1710.07505 [cs.DS], 2017.
R. Neininger and J. Straub, Probabilistic analysis of the dual-pivot quicksort "count", 2018 Proceedings of the Meeting of Analytic Algorithmics and Combinatorics, New Orleans, Louisiana, USA, 7pp.
Index entries for sequences related to sorting

Cf. A058312, A058313, A288964, A288970, A288971.

haralt := proc(n) local k: add((-1)^k/k, k = 1 .. n): end proc:
a := proc(n) local v, v1, v2: if n = 0 or n = 1 then v := 0: end if; if n = 2 then v := 2: end if: if n = 3 then v := 16: end if:
if 4 <= n then v1 := 9/5*n*harmonic(n) - 1/5*n*haralt(n) - 89/25*n + 67/40*harmonic(n) - 3/40*haralt(n) - 83/800 + 1/10*(-1)^n:
if 0 = n mod 2 then v2 := -1/320*1/(n - 3) - 3/320*1/(n - 1): end if:
if 1 = n mod 2 then v2 := 3/320*1/(n - 2) + 1/320*1/n: end if:
v := n!*(v1 + v2): end if: v: end proc:
seq(a(n1), n1 = 0 .. 30); # Petros Hadjicostas, May 03 2020

haralt[n_] := Sum[(-1)^k/k, {k, 1, n}];
a[n_] := Switch[n, 0|1, 0, 2, 2, 3, 16, _, n! ((9/5) n HarmonicNumber[n] - (1/5) n haralt[n] - (89/25) n + (67/40) HarmonicNumber[n] - (3/40)* haralt[n] - 83/800 + (-1)^n/10 - (Boole[EvenQ[n]]/320)(1/(n-3) + 3/(n-1)) + (Boole[OddQ[n]]/320)(3/(n-2) + 1/n))];
a /@ Range[0, 21] (* Jean-François Alcover, Jun 05 2020 *)

lista(nn) = {my(x='x + O('x^nn)); concat([0,0],Vec(serlaplace(-8*log(1-x)/(5*(1-x)^2) + 2*atanh(x)/(5*(1-x)^2) - 44/(25*(1-x)^2) - atanh(x)/(4*(1-x)) + 281/(160*(1-x)) + ((1-x)^3/320)*atanh(x) + x^3/150 - 27*x^2/1600 + 17*x/1600 + 3/800)))}; \\ Petros Hadjicostas and Michel Marcus, May 04 2020, e.g.f. from p. 29 in Aumüller et al. (2016)

a(n) = n!*((9/5)*n*Harmonic(n) - (1/5)*n*Harmonic_alt(n) - (89/25)*n + (67/40)*Harmonic(n) - (3/40)*Harmonic_alt(n) - 83/800 + (-1)^n/10 - ([n even]/320)*(1/(n - 3) + 3/(n - 1)) + ([n odd]/320)*(3/(n - 2) + 1/n)) for n >= 4, where [condition] = 1 if the condition holds, and 0 otherwise, and Harmonic_alt(n) = Sum_{k=1..n} (-1)^n/n = -A058313(n)/A058312(n). [This follows from Theorem 12.1 in Aumüller et al. (2016) or Theorem 5.7 in Aumüller et al. (2019).] - Petros Hadjicostas, May 03 2020

A067699 Number of comparisons made in a version of the sorting algorithm QuickSort for an array of size n with n identical elements.

Original entry on oeis.org

0, 4, 8, 14, 18, 24, 30, 38, 42, 48, 54, 62, 68, 76, 84, 94, 98, 104, 110, 118, 124, 132, 140, 150, 156, 164, 172, 182, 190, 200, 210, 222, 226, 232, 238, 246, 252, 260, 268, 278, 284, 292, 300, 310, 318, 328, 338, 350, 356, 364, 372, 382

Offset: 1

Karla J. Oty (oty(AT)uscolo.edu), Feb 05 2002

nonn

Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest. Introduction to Algorithms. McGraw-Hill Book Company, 2000. (Gives description of this version of QuickSort.)

Michael S. Branicky, Table of n, a(n) for n = 1..10000
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, preprint, 2016.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms 13:4 (2017), #47.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple generating functions, 2004.
Ralf Stephan, Table of generating functions (ps file).
Ralf Stephan, Table of generating functions (pdf file).

Cf. A063090, A076178, A093418, A096620, A115107, A288964.

from functools import cache
@cache
def b(n): return 0 if n == 0 else b(n//2) + b((n-1)//2) + n + 2 + (n&1)
def a(n): return b(n-1)
print([a(n) for n in range(1, 53)]) # Michael S. Branicky, Aug 08 2022

a(n) = 2*ceiling((n+1)/2)  + a(ceiling(n/2)) + a(floor(n/2)) with a(1) = 0, a(2) = 4 and a(3) = 8.
From Ralf Stephan, Oct 24 2003: (Start)
a(n) = A076178(n-1) + 4*(n-1) for n >= 1.
a(n) = b(n-1) for n >= 1, where b(0) = 0, b(2*n) = b(n) + b(n-1) + 2*n + 2, b(2*n+1) = 2*b(n) + 2*n + 4.
(End)

A288970 Number of key comparisons to sort all n! permutations of n elements by the optimal trial-pivot quicksort.

Original entry on oeis.org

0, 0, 2, 16, 112, 848, 7032, 64056, 639888, 6974928, 82531296, 1054724256, 14487894144, 212971227264

Offset: 0

Daniel Krenn, Jun 20 2017

The 3 pivot elements are chosen from fixed indices (e.g., the last 3 elements). The "optimal" strategy minimizes, after the choice of the pivots is done, the expected partitioning cost.

M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, arXiv:1510.04676 [cs.DS], 2016.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
Index entries for sequences related to sorting.

Cf. A001768, A003070, A036604, A117627, A117628, A159324, A288964, A288965, A288971.

a(9)-a(11) from Melanie Siebenhofer, Jan 29 2018

a(12)-a(13) from Melanie Siebenhofer, Feb 02 2018

A288971 Number of key comparisons to sort all n! permutations of n elements by the optimal quadral-pivot quicksort.

Original entry on oeis.org

0, 0, 2, 16, 112, 848, 7008, 63648, 635040, 6915168, 81757440, 1044161280, 14334076800, 210595524480

Offset: 0

Daniel Krenn, Jun 20 2017

The 4 pivot elements are chosen from fixed indices (e.g. the last 4 elements). The "optimal" strategy minimizes, after the choice of the pivots is done, the expected partitioning cost.

M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, ACM Transactions on Algorithms (TALG), Volume 13 Issue 1, 2016.
M. Aumüller and M. Dietzfelbinger, How Good Is Multi-Pivot Quicksort?, arXiv:1510.04676 [cs.DS], 2016.
Daniel Krenn, Quickstar, Program in SageMath, on GitHub.
Index entries for sequences related to sorting.

Cf. A288964, A288965, A288970.

a(9)-a(13) from Melanie Siebenhofer, Feb 05 2018

A330852 Numerator of the rational number A(n) that appears in the formula for the n-th cumulant k(n) = (-1)^n2^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.

Original entry on oeis.org

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

Offset: 0

Petros Hadjicostas, Apr 28 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 A(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 (-2)^n*A(n), which they denote by a_n. See also Finch (2020).
The Maple program below is based on Tan and Hadjicostas (1993), where the numbers (A(n): n >= 0) are also tabulated.
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).

			The first few fractions A(n) are
1, 0, 7/4, 19/8, 937/144, 85981/3456, 21096517/172800, 7527245453/10368000, 19281922400989/3810240000, 7183745930973701/177811200000, ...
The first few fractions (-2)^n*A(n) (= a_n in Hoffman and Kuba and in Finch) 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.]
James A. Fill and Svante Janson, Smoothness and decay properties of the limiting Quicksort density function, In: D. Gardy and A. Mokkadem (eds), Mathematics and Computer Science, Trends in Mathematics, Birkhäuser, Basel, 2000, pp. 53-64.
James A. Fill and Svante Janson, Quicksort asymptotics, Journal of Algorithms, 44(1) (2002), 4-28.
Steven Finch, Recursive PGFs for BSTs and DSTs, arXiv:2002.02809 [cs.DS], 2020; see Section 1.4. [He gives the constants a_s = (-2)^s*A(s) for s >= 2.]
P. Hennequin, Combinatorial analysis of the quicksort algorithm, Informatique théoretique et applications, 23(3) (1989), 317-333.
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 = (-2)^s*A(s) for s >= 2.]
Mireille Régnier, A limiting distribution for quicksort, Informatique théorique et applications, 23(3) (1989), 335-343.
Uwe Rösler, A limit theorem for quicksort, Informatique théorique et applications, 25(1) (1991), 85-100.
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.
Kok Hooi Tan and Petros Hadjicostas, Some properties of a limiting distribution in Quicksort, Statistics and Probability Letters, 25(1), 1995, 87-94.
Vytas Zacharovas, On the exponential decay of the characteristic function of the quicksort distribution, arXiv:1605.04018 [math.CO], 2016.

Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A330860 (denominators).

# Produces the sequence (B(n): n >= 0)
B := proc(m) option remember: local v, g, f, b:
if m = 0 then v := 1: end if: if m = 1 then v := 0: end if:
if 2 <= m then
g := proc(k) add((-1)^a*B(k - a)/(a!*(k - a)!*2^a), a = 0 .. k): end proc:
f := proc(r) add(Stirling1(r + 1, i + 1)*g(r - i), i = 0 .. r): end proc:
b := proc(p) (-1)^p*(add(Stirling1(p + 2, r + 1)*B(p - r)/(p - r)!, r = 1 .. p) + add(f(rr)*f(p - rr), rr = 1 .. p - 1) + 2*(-1)^p*p!*add((-1)^a*B(p - a)/(a!*(p - a)!*2^a), a = 1 .. p) + 2*add(Stirling1(p + 1, i + 1)*g(p - i), i = 1 .. p))/(p - 1): end proc:
v := simplify(b(m)): end if: v: end proc:
# Produces the sequence (A(n): n >= 0)
A := proc(m) option remember: local v:
if m = 0 then v := 1: end if: if m = 1 then v := 0: end if:
if 2 <= m then v := -(m - 1)!*add(A(k + 1)*B(m - 1 - k)/(k!*(m - 1 - k)!), k = 0 .. m - 2) + B(m): end if: v: end proc:
# Produces the sequence of numerators of the A(n)'s
seq(numer(A(n)), n = 0 .. 15);

B[m_] := B[m] = Module[{v, g, f, b}, If[m == 0, v = 1]; If[m == 1, v = 0]; If[2 <= m, g[k_] := Sum[(-1)^a*B[k - a]/(a!*(k - a)!*2^a), {a, 0, k}]; f[r_] := Sum[StirlingS1[r + 1, i + 1]*g[r - i], {i, 0, r}]; b[p_] := (-1)^p*(Sum[StirlingS1[p + 2, r + 1]*B[p - r]/(p - r)!, {r, 1, p}] + Sum[f[rr]*f[p - rr], {rr, 1, p - 1}] + 2*(-1)^p*p!*Sum[(-1)^a*B[p - a]/(a!*(p - a)!*2^a), {a, 1, p}] + 2*Sum[StirlingS1[p + 1, i + 1]*g[p - i], {i, 1, p}])/(p - 1); v = Simplify[b[m]]]; v];
A[m_] := A[m] = Module[{v}, If[ m == 0, v = 1]; If[m == 1, v = 0]; If[2 <= m , v = -(m - 1)!*Sum[A[k + 1]*B[m - 1 - k]/(k!*(m - 1 - k)!), {k , 0 , m - 2}] + B[m]]; v];
Table[Numerator[A[n]], {n, 0, 15}] (* Jean-François Alcover, Aug 17 2020, translated from Maple *)

A330860 Denominator of the rational number A(n) that appears in the formula for the n-th cumulant k(n) = (-1)^n2^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.

Original entry on oeis.org

1, 1, 4, 8, 144, 3456, 172800, 10368000, 3810240000, 177811200000, 9957427200000, 75278149632000000, 1912817782149120000000, 53023308921173606400000000, 17742659631203112173568000000000, 426249654980023566857797632000000000, 9600207854287580784554747166720000000000

Offset: 0

Petros Hadjicostas, Apr 28 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 A(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 (-2)^n*A(n), which they denote by a_n. See also Finch (2020).
The Maple program given in A330852 is based on Tan and Hadjicostas (1993), where the numbers (A(n): n >= 0) are also tabulated.
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.

			The first few fractions A(n) are
1, 0, 7/4, 19/8, 937/144, 85981/3456, 21096517/172800, 7527245453/10368000, 19281922400989/3810240000, 7183745930973701/177811200000, ...
The first few fractions (-2)^n*A(n) (= a_n in Hoffman and Kuba and in Finch) 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 = (-2)^s*A(s) for s >= 2.]
P. Hennequin, Combinatorial analysis of the quicksort algorithm, Informatique théoretique et applications, 23(3) (1989), 317-333.
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 = (-2)^s*A(s) 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.

Cf. A063090, A067699, A093418, A096620, A115107, A288964, A288965, A288970, A288971, A330852 (numerators).

# The function A is defined in A330852.
# Produces the sequence of denominators of the A(n)'s.
seq(denom(A(n)), n = 0 .. 40);

cp's OEIS Frontend

A093418 Numerator of -3*n + 2*(1+n)*HarmonicNumber(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A096620 Denominator of -3*n + 2*(1+n)*HarmonicNumber(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

Extensions

A063090 a(n)/(n*n!) is the average number of comparisons needed to find a node in a binary search tree containing n nodes inserted in a random order.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A115107 Numerator of q_n = -4*n + 2*(1+n)*HarmonicNumber(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Extensions

A288965 Number of key comparisons to sort all n! permutations of n elements by the optimal dual-pivot quicksort.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A067699 Number of comparisons made in a version of the sorting algorithm QuickSort for an array of size n with n identical elements.

Views

Author

Keywords

References

A093418 Numerator of -3n + 2(1+n)*HarmonicNumber(n).

A096620 Denominator of -3n + 2(1+n)*HarmonicNumber(n).

A115107 Numerator of q_n = -4n + 2(1+n)*HarmonicNumber(n).

A330852 Numerator of the rational number A(n) that appears in the formula for the n-th cumulant k(n) = (-1)^n2^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.

A330860 Denominator of the rational number A(n) that appears in the formula for the n-th cumulant k(n) = (-1)^n2^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.