login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A102379 a(n) = minimal number of nodes in a binary tree of height n. 1
0, 1, 2, 4, 6, 9, 12, 17, 22, 29, 36, 46, 56, 69, 82, 100, 118, 141, 164, 194, 224, 261, 298, 345, 392, 449, 506, 576, 646, 729, 812, 913, 1014, 1133, 1252, 1394, 1536, 1701, 1866, 2061, 2256, 2481, 2706, 2968, 3230, 3529, 3828, 4174, 4520, 4913 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

REFERENCES

de Bruijn, N. G., On Mahler's partition problem. Nederl. Akad. Wetensch., Proc. 51, (1948) 659-669 = Indagationes Math. 10, 210-220 (1948).

Gonnet, Gaston H.; Olivie, Henk J.; and Wood, Derick, Height-ratio-balanced trees. Comput. J. 26 1983), no. 2, 106-108.

Mahler, Kurt On a special functional equation. J. London Math. Soc. 15, (1940). 115-123.

Nievergelt, J.; Reingold, E. M., Binary search trees of bounded balance, SIAM J. Comput. 2 (1973), 33-43.

LINKS

Table of n, a(n) for n=1..50.

FORMULA

a(n) = a(n-1) + a([n/2]) + 1, a(1) = 0

a(n) - a(n-1) = A018819(n+1)

gf A(x) satisfies (1-x)*A(x) = 2(1 + x)*B(x^2), where B(x) is the gf of A033485

CROSSREFS

Cf. A000123, A033485, A102378.

Sequence in context: A064985 A090631 A001365 * A238374 A133041 A079492

Adjacent sequences:  A102376 A102377 A102378 * A102380 A102381 A102382

KEYWORD

nonn

AUTHOR

Mitch Harris, Jan 05 2005

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 14:20 EDT 2018. Contains 316380 sequences. (Running on oeis4.)