A195601 -id:A195601 - cp's OEIS frontend

A195582 Numerator of the average height of a binary search tree on n elements.

0, 1, 2, 8, 10, 19, 64, 1471, 3161, 3028, 6397, 27956, 58307, 168652, 190031, 794076401, 817191437, 57056556523, 65776878541, 112508501827291, 32836043478431, 24620974441660973, 30663050241335933, 280904716386831931, 1713934856212591039, 12438570098319186469

Offset: 0

Alois P. Heinz, Sep 20 2011

Empty external nodes are counted in determining the height of a search tree.

			0/1, 1/1, 2/1, 8/3, 10/3, 19/5, 64/15, 1471/315, 3161/630, 3028/567, 6397/1134, 27956/4725, 58307/9450, 168652/26325, 190031/28665 ... = A195582/A195583
For n = 3 there are 2 permutations of {1,2,3} resulting in a binary search tree of height 2 and 4 permutations resulting in a tree of height 3.  The average height is (2*2+4*3)/3! = (4+12)/6 = 16/6 = 8/3.

Alois P. Heinz, Table of n, a(n) for n = 0..478
B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Denominators: A195583.

Cf. A000142, A195581, A195596, A195597, A195598, A195599, A195600, A195601, A244108, A316944.

b:= proc(n,k) option remember;
      if n=0 then 1
    elif n=1 then `if`(k>0, 1, 0)
    else add(binomial(n-1,r-1) *b(r-1,k-1) *b(n-r,k-1), r=1..n)
      fi
    end:
T:= (n, k)-> b(n, k)-`if`(k>0, b(n, k-1), 0):
a:= n-> add(T(n,k)*k, k=0..n)/n!:
seq(numer(a(n)), n=0..30);

b[n_, k_] := b[n, k] = If[n==0, 1, If[n==1, If[k>0, 1, 0], Sum[Binomial[n - 1, r-1]*b[r-1, k-1]*b[n-r, k-1], {r, 1, n}]]]; T[n_, k_] := b[n, k] - If[ k>0, b[n, k-1], 0]; a[n_] := Sum[T[n, k]*k, {k, 0, n}]/n!; Table[ Numerator[a[n]], {n, 0, 30}] (* Jean-François Alcover, Mar 01 2016, after Alois P. Heinz *)

A195582(n)/A195583(n) = 1/n! * Sum_{k=1..n} k * A195581(n,k).
A195582(n)/A195583(n) = alpha*log(n) - beta*log(log(n)) + O(1), with alpha = 4.311... (A195596) and beta = 1.953... (A195599).
A195582(n)/A195583(n) = A316944(n) / A000142(n).

A195596 Decimal expansion of alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.

Original entry on oeis.org

4, 3, 1, 1, 0, 7, 0, 4, 0, 7, 0, 0, 1, 0, 0, 5, 0, 3, 5, 0, 4, 7, 0, 7, 6, 0, 9, 6, 4, 4, 6, 8, 9, 0, 2, 7, 8, 3, 9, 1, 5, 6, 2, 9, 9, 8, 0, 4, 0, 2, 8, 8, 0, 5, 0, 6, 6, 9, 3, 7, 8, 8, 4, 4, 4, 6, 2, 4, 8, 2, 9, 5, 7, 4, 9, 5, 1, 4, 1, 6, 6, 4, 6, 0, 1, 4, 9, 5, 6, 4, 3, 9, 4, 4, 1, 4, 4, 9, 0, 9, 6, 6, 9, 0, 1

Offset: 1

Alois P. Heinz, Sep 21 2011

alpha is used to measure the expected height of random binary search trees.

			4.31107040700100503504707609644689027839156299804028805066937...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.13 Binary search tree constants, p. 352.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Luc Devroye, A note on the height of binary search trees, Journal of the ACM, Vol. 33, No. 3 (1986), pp. 489-498.
Bruce Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.
John Michael Robson, The height of binary search trees, Australian Computer Journal, Vol. 11, No. 4 (1979), pp. 151-153. [broken link]
Larry Shepp, Doron Zeilberger and Cun-Hui Zhang, Pick up sticks, arXiv preprint arXiv:1210.5642 [math.CO] (2012).
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A195597 (continued fraction), A195598 (Engel expansion), A195581, A195582, A195583, A195599, A195600, A195601.

alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
as:= convert(evalf(alpha/10, 130), string):
seq(parse(as[n+1]), n=1..120);

RealDigits[ -1/ProductLog[-1/(2*E)] , 10, 105] // First (* Jean-François Alcover, Feb 19 2013 *)

alpha = -1/W(-exp(-1)/2), where W is the Lambert W function.

A195582(n)/A195583(n) = alpha*log(n) - beta*log(log(n)) + O(1), with beta = 1.953... (A195599).

A195599 Decimal expansion of beta = 3/(2*log(alpha/2)), where alpha = A195596.

Original entry on oeis.org

1, 9, 5, 3, 0, 2, 5, 7, 0, 3, 3, 5, 8, 1, 5, 4, 1, 3, 9, 4, 5, 4, 0, 6, 2, 8, 8, 5, 4, 2, 5, 7, 5, 3, 8, 0, 4, 1, 4, 2, 5, 1, 3, 4, 0, 2, 0, 1, 0, 3, 6, 3, 1, 9, 6, 0, 9, 3, 5, 4, 2, 8, 8, 1, 8, 0, 6, 9, 6, 0, 7, 9, 7, 2, 3, 3, 6, 2, 5, 2, 5, 6, 9, 7, 5, 2, 1, 8, 9, 2, 9, 5, 3, 3, 5, 3, 1, 5, 1, 9, 7, 3, 2, 3, 1

Offset: 1

Alois P. Heinz, Sep 21 2011

beta is used to measure the expected height of random binary search trees.

			1.95302570335815413945406288542575380414251340201036319609354...

Alois P. Heinz, Table of n, a(n) for n = 1..10000
B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.
Wikipedia, Binary search tree
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A195600 (continued fraction), A195601 (Engel expansion), A195581, A195582, A195583, A195596, A195597, A195598.

alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
beta:= 3/(2*log(alpha/2)):
bs:= convert(evalf(beta/10, 130), string):
seq(parse(bs[n+1]), n=1..120);

RealDigits[ 3/(2 + 2*ProductLog[-1/(2*E)]) , 10, 105] // First (* Jean-François Alcover, Feb 19 2013 *)

beta = 3/(2*log(alpha/2)) = 3*alpha/(2*alpha-2), where alpha = A195596 = -1/W(-exp(-1)/2) and W is the Lambert W function.

A195582(n)/A195583(n) = alpha*log(n) - beta*log(log(n)) + O(1).

A195600 Continued fraction for beta = 3/(2*log(alpha/2)); alpha = A195596.

Original entry on oeis.org

1, 1, 20, 3, 2, 7, 1, 1, 1, 12, 1, 5, 1, 91, 1, 1, 3, 87, 2, 1, 1, 1, 1, 3, 1, 9, 3, 2, 1, 1, 1, 1, 190, 1, 3, 1, 82, 2, 1, 1, 1, 2, 1, 1, 1, 6, 1, 2, 12, 6, 2, 2, 2, 3, 2, 1, 1, 1, 2, 3, 21, 1, 1, 12, 1, 7, 3, 2, 26, 3, 2, 1, 1, 1, 9, 1, 15, 4, 3, 3, 1, 3, 1

Offset: 0

Alois P. Heinz, Sep 21 2011

beta is used to measure the expected height of random binary search trees.

			1.95302570335815413945406288542575380414251340201036319609354...

B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.

Cf. A195599 (decimal expansion), A195601 (Engel expansion), A195581, A195582, A195583, A195596, A195597, A195598.

with(numtheory):
alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
beta:= 3/(2*log(alpha/2)):
cfrac(evalf(beta, 130), 100, 'quotients')[];

beta = 3/(2+2*ProductLog[-1/(2*E)]); ContinuedFraction[beta, 83] (* Jean-François Alcover, Jun 20 2013 *)

beta = 3/(2*log(alpha/2)) = 3*alpha/(2*alpha-2), where alpha = A195596 = -1/W(-exp(-1)/2) and W is the Lambert W function.

A195582(n)/A195583(n) = alpha*log(n) - beta*log(log(n)) + O(1).

Offset changed by Andrew Howroyd, Jul 03 2024

A195597 Continued fraction for alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.

Original entry on oeis.org

4, 3, 4, 1, 1, 1, 11, 2, 19, 1, 3, 1, 1, 1, 14, 1, 3, 5, 58, 3, 1, 10, 1, 1, 6, 5, 13, 127, 1, 1, 7, 13, 1, 2, 1, 2, 2, 1, 2, 2, 4, 2, 4, 1, 1, 6, 9, 3, 1, 16, 1, 3, 2, 32, 3, 1, 1, 2, 11, 1, 13, 4, 2, 1, 1, 1, 1, 2, 2, 6, 1, 1, 1, 2, 25, 1, 5, 5, 1, 1, 1, 1, 5, 2, 3, 2, 5, 25, 1, 190, 2, 1, 5, 3, 1, 20, 1, 1, 2, 1, 3

Offset: 0

Alois P. Heinz, Sep 21 2011

alpha is used to measure the expected height of random binary search trees.

			4.31107040700100503504707609644689027839156299804028805066937...

B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.

Cf. A195596 (decimal expansion), A195598 (Engel expansion), A195581, A195582, A195583, A195599, A195600, A195601.

with(numtheory):
alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
cfrac(evalf(alpha, 130), 100, 'quotients')[];

alpha = -1/ProductLog[-1/(2*E)]; ContinuedFraction[alpha, 101] (* Jean-François Alcover, Jun 20 2013 *)

alpha = -1/W(-exp(-1)/2), where W is the Lambert W function.

A195582(n)/A195583(n) = alpha*log(n) - beta*log(log(n)) + O(1), with beta = 1.953... (A195599).

Offset changed by Andrew Howroyd, Jul 03 2024

A195598 Engel expansion of alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.

Original entry on oeis.org

1, 1, 1, 1, 4, 5, 5, 10, 15, 18, 102, 114, 246, 394, 1051, 3044, 50263, 111686, 128162, 273256, 583069, 927699, 7299350, 10833746, 15187876, 67314562, 2141820499, 4969978969, 10131201410, 49316153957, 221808008142, 275241196373, 1466049587038, 3406190692970

Offset: 1

Alois P. Heinz, Sep 21 2011

nonn

alpha = 4.31107040700100503504707609644689027839156299804028805066937... is used to measure the expected height of random binary search trees.

Cf. A006784 for definition of Engel expansion.

F. Engel, Entwicklung der Zahlen nach Stammbrüchen, Verhandlungen der 52. Versammlung deutscher Philologen und Schulmänner in Marburg, 1913, pp. 190-191.

F. Engel, Entwicklung der Zahlen nach Stammbruechen, Verhandlungen der 52. Versammlung deutscher Philologen und Schulmaenner in Marburg, 1913, pp. 190-191. English translation by Georg Fischer, included with his permission.
P. Erdős and Jeffrey Shallit, New bounds on the length of finite Pierce and Engel series, Sem. Theor. Nombres Bordeaux (2) 3 (1991), no. 1, 43-53.
B. Reed, The height of a random binary search tree, J. ACM, 50 (2003), 306-332.
Eric Weisstein's World of Mathematics, Engel Expansion
Wikipedia, Engel Expansion
Index entries for sequences related to Engel expansions

Cf. A195596 (decimal expansion), A195597 (continued fraction), A195581, A195582, A195583, A195599, A195600, A195601.

alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
engel:= (r, n)-> `if`(n=0 or r=0, NULL, [ceil(1/r), engel(r*ceil(1/r)-1, n-1)][]):
Digits:=400: engel(evalf(alpha), 39);

alpha = -1/W(-exp(-1)/2), where W is the Lambert W function.

A195582(n)/A195583(n) = alpha*log(n) - beta*log(log(n)) + O(1), with beta = 1.953... (A195599).

cp's OEIS Frontend

A195582 Numerator of the average height of a binary search tree on n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A195596 Decimal expansion of alpha, the unique solution on [2,oo) of the equation alpha*log((2*e)/alpha)=1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A195599 Decimal expansion of beta = 3/(2*log(alpha/2)), where alpha = A195596.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A195600 Continued fraction for beta = 3/(2*log(alpha/2)); alpha = A195596.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A195597 Continued fraction for alpha, the unique solution on [2,oo) of the equation alpha*log((2*e)/alpha)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A195598 Engel expansion of alpha, the unique solution on [2,oo) of the equation alpha*log((2*e)/alpha)=1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Formula

A195596 Decimal expansion of alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.

A195597 Continued fraction for alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.

A195598 Engel expansion of alpha, the unique solution on [2,oo) of the equation alphalog((2e)/alpha)=1.