cp's OEIS Frontend

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

%I A093418 #109 Feb 16 2025 08:32:53
%S A093418 0,1,3,17,53,62,163,717,3489,3727,43391,45596,619313,644063,667229,
%T A093418 2756003,24124223,24784883,160941559,164719333,33664415,11451017,
%U A093418 268428987,819836496,20845424563,21181779967,193553388003,196368607553,5773568883787,5849866645327
%N A093418 Numerator of -3*n + 2*(1+n)*HarmonicNumber(n).
%C A093418 Numerator of the average time to quicksort n items in random order.
%C A093418 From _Petros Hadjicostas_, Oct 20 2019: (Start)
%C A093418 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.
%C A093418 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.
%C A093418 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)).
%C A093418 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).
%C A093418 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)).
%C A093418 (End)
%D A093418 Peter J. Cameron, Combinatorics: Topics, Techniques and Algorithms, Cambridge Univ. Press, 1996; see pp. 66-68.
%D A093418 J. H. Conway and R. K. Guy, The Book of Numbers. New York: Springer-Verlag, 1996, pp. 143 and 258-259.
%D A093418 Julian Havil, Gamma: Exploring Euler's constant, Princeton University Press, 2003; see pp. 128-130.
%D A093418 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 3, 1998; see pp. 427-431 and 454-455.
%H A093418 G. C. Greubel, <a href="/A093418/b093418.txt">Table of n, a(n) for n = 0..1000</a> [recomputed for offset 0 by _Georg Fischer_, Oct 13 2019]
%H A093418 S. B. Ekhad and D. Zeilberger, <a href="https://arxiv.org/abs/1903.03708">A detailed analysis of quicksort running time</a>, 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.]
%H A093418 M. Kauers and P. Paule, <a href="https://doi.org/10.1007/978-3-7091-0445-3">The Concrete Tetrahedron</a>, Springer, 2011; see p. 4. [They agree with Cameron's recurrence and the numerators are in A115107.]
%H A093418 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Quicksort.html">Quicksort</a>. [He uses Havil's recurrence.]
%H A093418 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HarmonicNumber.html">Harmonic Number</a>.
%H A093418 Wikipedia, <a href="https://en.wikipedia.org/wiki/Quicksort">Quicksort</a>. [Uses Cameron's recurrence and the numerators are in A115107.]
%F A093418 G.f. for fractions fr(n): -(x+2*log(1-x))/(1-x)^2. - _Vladeta Jovovic_, Jul 05 2004
%F A093418 a(n) = 1 + (1/n!) * Sum_{k=0..n} (-1)^(n-k) * Stirling1(n, k) * (k-1) * 2^k. - _Vladeta Jovovic_, Jul 05 2004
%F A093418 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
%e A093418 fr(n) = 0, 1, 3, 17/3, 53/6, 62/5, 163/10, 717/35, 3489/140, ... = A093418/A096620.
%p A093418 a := n -> numer(2*(n + 1)*(Psi(n + 1) + gamma) - 3*n);
%p A093418 seq(a(n), n=0..26); # _Peter Luschny_, Aug 26 2019
%t A093418 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}]]
%t A093418 Numerator[Table[2*(n+1)*HarmonicNumber[n] - 3*n, {n, 0, 50}]] (* _G. C. Greubel_, Sep 01 2018 *)
%o A093418 (PARI) {h(n) = sum(k=1,n,1/k)};
%o A093418 for(n=0,50, print1(numerator(2*(n+1)*h(n) -3*n), ", ")) \\ _G. C. Greubel_, Sep 01 2018
%o A093418 (Magma) [Numerator(2*(n+1)*HarmonicNumber(n) -3*n): n in [0..50]]; // _G. C. Greubel_, Sep 01 2018
%o A093418 (Python)
%o A093418 from fractions import Fraction
%o A093418 from itertools import count, islice
%o A093418 def agen(): # generator of terms
%o A093418     Hn = Fraction(0, 1)
%o A093418     for n in count(0):
%o A093418         yield (-3*n + 2*(1+n)*Hn).numerator
%o A093418         Hn += Fraction(1, n+1)
%o A093418 print(list(islice(agen(), 27))) # _Michael S. Branicky_, Apr 17 2022
%Y A093418 Cf. A001008, A002805, A063090, A096620, A115107, A288964.
%Y A093418 The denominators in A096620 are essentially the same as the numbers in A093419, which are the denominators of A093412.
%K A093418 nonn,frac
%O A093418 0,3
%A A093418 _Amarnath Murthy_, Mar 30 2004
%E A093418 Edited by _Eric W. Weisstein_, Jul 01 2004
%E A093418 Offset changed to 0 by _Petros Hadjicostas_, Aug 26 2019