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

%I #19 Jul 24 2022 06:57:20

%S 0,1,2,4,6,9,12,17,22,29,36,46,56,69,82,100,118,141,164,194,224,261,

%T 298,345,392,449,506,576,646,729,812,913,1014,1133,1252,1394,1536,

%U 1701,1866,2061,2256,2481,2706,2968,3230,3529,3828,4174,4520,4913

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

%C 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

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

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

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

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

%F a(n) = a(n-1) + a(floor(n/2)) + 1, a(1) = 0.

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

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

%o (Python)

%o from functools import cache

%o @cache

%o def a(n: int) -> int:

%o return a(n - 1) + a(n // 2) + 1 if n > 1 else 0

%o print([a(n) for n in range(1, 51)]) # _Peter Luschny_, Jul 24 2022

%Y Cf. A000123, A033485, A102378.

%Y Essentially partial sums of A040039.

%K nonn

%O 1,3

%A _Mitch Harris_, Jan 05 2005