A102379 a(n) is the minimal number of nodes in a binary tree of height n.

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

Offset

1,3

Comments

Conjecture: Let b(n) be the number of fixed points of the set of binary partitions of n under Glaisher's function that proves Euler's odd-distinct theorem. Then b(1) = 1 and for n > 1, b(2*n) = b(2*n+1) = 2*a(n). - George Beck, Jul 23 2022

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(floor(n/2)) + 1, a(1) = 0.

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

G.f. A(x) satisfies (1-x)*A(x) = 2*(1 + x)*B(x^2), where B(x) is the g.f. of A033485.

Prog

(Python)
from functools import cache
@cache
def a(n: int) -> int:
    return a(n - 1) + a(n // 2) + 1 if n > 1 else 0
print([a(n) for n in range(1, 51)])  # Peter Luschny, Jul 24 2022

Crossrefs

Cf. A000123, A033485, A102378.

Essentially partial sums of A040039.

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