A195596 -id:A195596 - cp's OEIS frontend

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

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

A195601 Engel expansion of beta = 3/(2*log(alpha/2)); alpha = A195596.

Original entry on oeis.org

1, 2, 2, 2, 2, 5, 5, 5, 20, 36, 78, 842, 5291, 10373, 17340, 28619, 35586, 93572, 98045, 2470364, 13603654, 14328528, 16490766, 833971648, 1788088151, 9592330101, 10952282168, 40005288076, 54302548920, 118523737357, 776601533408, 1241894797770, 24485470725324

Offset: 1

Alois P. Heinz, Sep 21 2011

nonn

beta = 1.95302570335815413945406288542575380414251340201036319609354... 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.

G. C. Greubel, Table of n, a(n) for n = 1..1000
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. A195599 (decimal expansion), A195600 (continued fraction), A195581, A195582, A195583, A195596, A195597, A195598.

alpha:= solve(alpha*log((2*exp(1))/alpha)=1, alpha):
beta:= 3/(2*log(alpha/2)):
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(beta), 39);

f:= N[-1/ProductLog[-1/(2*E)], 500001]; EngelExp[A_, n_]:= Join[Array[1 &, Floor[A]], First@Transpose@NestList[{Ceiling[1/Expand[#[[1]] #[[2]] - 1]], Expand[#[[1]] #[[2]] - 1]} &, {Ceiling[1/(A - Floor[A])], A - Floor[A]}, n - 1]]; EngelExp[N[3/(2*Log[f/2]), 500000], 25] (* G. C. Greubel, Oct 21 2016 *)

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

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

Original entry on oeis.org

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

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

A243398 Decimal expansion of the limiting length appearing in the asymptotic probability involved in the "stick breaking" problem.

Original entry on oeis.org

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

Offset: 1

Jean-François Alcover, Jun 04 2014

			1.26107048683067890583965514796261283...

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

Cf. A195596.

c = -1/ProductLog[-1/(2*E)]; RealDigits[Exp[1/c], 10, 100] // First

exp(1/c), where c is A195596.

A242461 Decimal expansion of the first positive solution to exp(1-1/x)/x = 1/2, a binary search tree constant.

Original entry on oeis.org

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

Offset: 0

Jean-François Alcover, May 15 2014

The saturation level S_n of a binary search tree defined by a random n-permutation is such that S_n/log(n) converges to 0.3733646... in probability.

			0.373364617701674084248448436679270595...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, pp. 349-352.

Luc Devroye, A Note on the Height of Binary Search Trees. McGill University, Montreal, Canada (1986).

Cf. A076615, A076616, A195581, A195582, A195596.

RealDigits[-1/ProductLog[-1, -1/(2*E)], 10, 100] // First

-1/W(-1, -1/(2*e)) where W is the Lambert W function (ProductLog).

cp's OEIS Frontend

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

A195601 Engel expansion of beta = 3/(2*log(alpha/2)); alpha = A195596.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

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

A243398 Decimal expansion of the limiting length appearing in the asymptotic probability involved in the "stick breaking" problem.

Views

Author

Keywords

Examples

References

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.