OFFSET
0,2
COMMENTS
a(n) is the minimum number of nodes required for a full binary tree where each node in all longest paths from the root node down to any leaf node is height-balanced and the root node has a height balance factor of 0.
Full binary tree: A binary tree is called a full binary tree if each node has exactly two children or no children.
LINKS
Michael De Vlieger, Table of n, a(n) for n = 0..10000
Lecture Notes for Computer Science 2530, Height-balanced trees
NIST, Root node
NIST, Leaf node
Wikipedia, Full binary tree
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).
FORMULA
a(n) = 2*A027688(n-2) + 1, for n >= 2.
a(n) = 4*A022856(n+2) - 1, for n >= 1.
a(n) = a(n-1) + 4*(n-2) for n >= 3.
G.f.: (1 + x^2 - 2*x^3 + 4*x^4)/(1 - x)^3. - Stefano Spezia, Jun 12 2022
Sum_{n>=2} 1/a(n) = Pi*tanh(sqrt(13)*Pi/2)/(2*sqrt(13)). - Amiram Eldar, Jul 10 2022
EXAMPLE
The diagrams below illustrate the terms a(3)=11 and a(4)=19.
R R
/ \ / \
/ \ / \
/ \ / \
o o / \
/ \ / \ / \
o N N o / \
/ \ / \ / \
N N N N o o
/ \ / \
/ \ / \
/ \ / \
o o o o
/ \ / \ / \ / \
o N N N N N o N
/ \ / \
N N N N
MATHEMATICA
CoefficientList[Series[(1 + x^2 - 2 x^3 + 4 x^4)/(1 - x)^3, {x, 0, 51}], x] (* Michael De Vlieger, Jun 19 2022 *)
PROG
(C) int a(int n){ return n>1 ? 2*(n*n) - 6*n + 11 : 2*n + 1; }
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Sumukh Patel, Jun 11 2022
STATUS
approved