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

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

Author

N. J. A. Sloane, Mar 07 2006

Keywords

• nonn
• frac

Comments

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)

Examples

			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)
		

References

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

Links

• 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.]

Crossrefs

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

Programs

Magma

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

Mathematica

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

PARI

{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

Python

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

Extensions

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