A093419 -id:A093419 - 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

A093422 In the triangle shown below the n-th row contains n rational numbers n/1, {n(n-1)}/{n +(n-1)}, {(n)(n-1)(n-2)}/{n +(n-1)+(n-2)}, ..., the last term being 2(n-1)!/(n+1). Sequence gives the numerators in each row.

Original entry on oeis.org

1, 2, 2, 3, 6, 1, 4, 12, 8, 12, 5, 20, 5, 60, 8, 6, 30, 8, 20, 36, 240, 7, 42, 35, 420, 504, 560, 180, 8, 56, 16, 840, 224, 6720, 1152, 1120, 9, 72, 21, 504, 432, 20160, 4320, 90720, 8064, 10, 90, 80, 2520, 756, 3360, 86400, 453600, 67200, 725760, 11, 110, 33, 3960

Offset: 1

Amarnath Murthy, Mar 30 2004

			Triangle of fractions starts
  1,
  2, 2/3,
  3, 6/5, 1,
  4, 12/7, 8/3, 12/5,
  5, 20/9, 5, 60/7, 8,
  6, 30/11, 8, 20, 36, 240/7,
  7, 42/13, 35/3, 420/11, 504/5, 560/3, 180,
  8, 56/15, 16, 840/13, 224, 6720/11, 1152, 1120,
  9, 72/17, 21, 504/5, 432, 20160/13, 4320, 90720/11, 8064,

G. C. Greubel, Rows n=0..100 of triangle, flattened

Cf. A093412, A093413, A093414, A093415, A093417, A093418, A093419, A093420, A093421, A093423.

/* as a triangle */ [[k le 1 select n else Numerator(2*Binomial(n,k)*Factorial(k-1)/(2*n-k+1)): k in [1..n]]: n in [1..10]]; // G. C. Greubel, Sep 01 2018

A09342x := proc(n,m) local i,N,D ; N := n ; if m = 1 then D := 1 ; else D := n ; end ; for i from 1 to m-1 do N := N*(n-i) ; D := D+n-i ; od ; simplify(N/D) ; end: A093422 := proc(n,m) numer(A09342x(n,m)) ; end: for n from 1 to 12 do for m from 1 to n do printf("%d, ",A093422(n,m)) ; od ; od ; # R. J. Mathar, Apr 28 2007

Table[If[k == 1, n, Numerator[2*Binomial[n,k]*(k-1)!/(2*n-k+1)]], {n,1,30}, {k,1,n}]//Flatten (* G. C. Greubel, Sep 01 2018 *)

for(n=1,10, for(k=1,n, print1(if(k==1, n, denominator(2*binomial(n,k)*(k-1)!/(2*n-k+1))), ", "))) \\ G. C. Greubel, Sep 01 2018

A093422(n,m)/A093423(n,m) = 2*binomial(n,m)*(m-1)!/(2*n-m+1) for 2 <= m < n. A093422(n,1)/A093423(n,1)= n. - R. J. Mathar, Apr 28 2007

More terms from R. J. Mathar, Apr 28 2007

A093423 Consider the triangle whose first part is shown as an example in the entry A093422. If the n-th term of the triangle read by rows is a fraction then a(n) is the denominator of the fraction, otherwise a(n)=1.

Original entry on oeis.org

1, 1, 3, 1, 5, 1, 1, 7, 3, 5, 1, 9, 1, 7, 1, 1, 11, 1, 1, 1, 7, 1, 13, 3, 11, 5, 3, 1, 1, 15, 1, 13, 1, 11, 1, 1, 1, 17, 1, 5, 1, 13, 1, 11, 1, 1, 19, 3, 17, 1, 1, 7, 13, 1, 11, 1, 21, 1, 19, 1, 17, 1, 1, 1, 13, 1, 1, 23, 1, 7, 5, 19, 1, 17, 1, 1, 1, 13

Offset: 1

Amarnath Murthy, Mar 30 2004

			Triangle begins:
  1;
  1,  3;
  1,  5,  1;
  1,  7,  3,  5;
  1,  9,  1,  7,  1;
  1, 11,  1,  1,  1,  7;
  1, 13,  3, 11,  5,  3,  1;
  1, 15,  1, 13,  1, 11,  1,  1;
  ...

G. C. Greubel, Rows n=1..100 of triangle, flattened

Cf. A093412, A093413, A093414, A093415, A093417, A093418, A093419, A093420, A093421, A093422.

/* as a triangle */ [[Denominator(2*Binomial(n,k)*Factorial(k-1)/(2*n-k+1)): k in [1..n]]: n in [1..30]]; // G. C. Greubel, Sep 01 2018

A09342x := proc(n,m) local a,i,N,D ; N := n ; if m = 1 then D := 1 ; else D := n ; end ; for i from 1 to m-1 do N := N*(n-i) ; D := D+n-i ; od ; simplify(N/D) ; end: A093423 := proc(n,m) denom(A09342x(n,m)) ; end: for n from 1 to 12 do for m from 1 to n do printf("%d, ",A093423(n,m)) ; od ; od ; # R. J. Mathar, Apr 28 2007

Table[Denominator[2*Binomial[n,k]*(k-1)!/(2*n-k+1)], {n,1,30}, {k,1,n}]//Flatten (* G. C. Greubel, Sep 01 2018 *)

for(n=1,10, for(k=1,n, print1(denominator(2*binomial(n,k)*(k-1)!/(2*n-k+1)), ", "))) \\ G. C. Greubel, Sep 01 2018

A093422(n,m)/A093423(n,m) = 2*binomial(n,m)*(m-1)!/(2*n-m+1) for 2 <= m < n. A093422(n,1)/A093423(n,1)= n. - R. J. Mathar, Apr 28 2007

More terms from R. J. Mathar, Apr 28 2007

Better definition from Omar E. Pol, Jan 10 2009

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

A093422 In the triangle shown below the n-th row contains n rational numbers n/1, {n*(n-1)}/{n +(n-1)}, {(n)*(n-1)*(n-2)}/{n +(n-1)+(n-2)}, ..., the last term being 2*(n-1)!/(n+1). Sequence gives the numerators in each row.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A093423 Consider the triangle whose first part is shown as an example in the entry A093422. If the n-th term of the triangle read by rows is a fraction then a(n) is the denominator of the fraction, otherwise a(n)=1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

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

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

A093422 In the triangle shown below the n-th row contains n rational numbers n/1, {n(n-1)}/{n +(n-1)}, {(n)(n-1)(n-2)}/{n +(n-1)+(n-2)}, ..., the last term being 2(n-1)!/(n+1). Sequence gives the numerators in each row.