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

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

Author

Jean-François Alcover, May 15 2014

Keywords

• nonn
• cons

Comments

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.

Examples

			0.373364617701674084248448436679270595...
		

References

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

Links

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

Crossrefs

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

Programs

Mathematica

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

Formula

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