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

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,1

Comments

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

References

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

Links

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

Formula

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

Example

4.31107040700100503504707609644689027839156299804028805066937...

Maple

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

Mathematica

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

Crossrefs

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

Sequence in context: A327334 A354794 A355401 * A332054 A129810 A016500

Adjacent sequences: A195593 A195594 A195595 * A195597 A195598 A195599

Keyword

nonn,cons

Author

Alois P. Heinz, Sep 21 2011

Status

approved