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

Author

Mitch Harris, Jan 05 2005

Keywords

• nonn

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.

Crossrefs

Cf. A000123, A033485, A102378.

Essentially partial sums of A040039.

Programs

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

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.