login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A187131 Numerator of probability that the height of a rooted random binary tree is n 1
1, 1, 9, 1521, 71622369, 233297499911422401, 3390052406222940758260506721830900609, 934785860242188709610961043825803400592180434378516146129897302939414193921 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

If each node of a rooted random binary tree has probability 1/2 of producing two branches, and p(n) is the probability that the height of the tree is n, then p(n) has the following properties:

* p(n) = 2*b(n+1)^2 with b(n) defined as in A076628;

* p(n+1) = p(n)*(1 - sqrt(p(n)/2))^2 starting from p(0)=1/2;

* Sum_n p(n) = 1;

* Sum_n n*p(n) is infinite;

* p(n) = a(n) / 2^(2^(n+1)-1).

LINKS

Table of n, a(n) for n=0..7.

FORMULA

a(n) = A076628(n)^2.

EXAMPLE

For n=0 the root node may have no branches giving the tree height 0, so p(0)=1/2 and a(0)=1; p(1) = 1/2*1/4 = 1/8 so a(1)=1; p(2) = 1/4*1/4 + 1/8*1/16 = 9/128 so a(2)=9; p(3) = 5/32*1/4 + 7/64*1/16 + 1/32*1/64 + 1/128*1/256 = 1521/32768 so a(3)=1521.

CROSSREFS

Denominator is A058891 offset

Sequence in context: A217267 A300594 A203649 * A167774 A197206 A197804

Adjacent sequences:  A187128 A187129 A187130 * A187132 A187133 A187134

KEYWORD

nonn

AUTHOR

Henry Bottomley, Mar 05 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 24 20:34 EST 2020. Contains 338616 sequences. (Running on oeis4.)