|
| |
|
|
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; 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.
|
|
|
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 * A133041 A079492 A173784
Adjacent sequences: A102376 A102377 A102378 * A102380 A102381 A102382
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Mitch Harris (harris (AT) tcs.inf.tu-dresden.de) Jan 05 2005
|
| |
|
|
