login
A195596
Decimal expansion of alpha, the unique solution on [2,oo) of the equation alpha*log((2*e)/alpha)=1.
9
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
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).
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
KEYWORD
nonn,cons
AUTHOR
Alois P. Heinz, Sep 21 2011
STATUS
approved