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!)
 A096620 Denominator of -3*n + 2*(1+n)*HarmonicNumber(n). 18
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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 contating 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) 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 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.] FORMULA 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) EXAMPLE 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) MATHEMATICA Denominator[Table[2*(n + 1)*HarmonicNumber[n + 1] - 1, {n, 0, 50}]] (* G. C. Greubel, Sep 01 2018 *) PROG (PARI) {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 (MAGMA) [Denominator(2*(n+1)*HarmonicNumber(n+1) -1): n in [0..50]]; // G. C. Greubel, Sep 01 2018 CROSSREFS Cf. A063090, A093418 (one set of numerators), A115107 (another set of numerators), A288964. Essentially the same as A093419. Sequence in context: A127780 A118413 A295320 * A093419 A160049 A331124 Adjacent sequences:  A096617 A096618 A096619 * A096621 A096622 A096623 KEYWORD nonn,frac AUTHOR Eric W. Weisstein, Jul 01 2004 EXTENSIONS Offset corrected by Gary Detlefs, Sep 14 2011 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 October 19 21:34 EDT 2021. Contains 348095 sequences. (Running on oeis4.)