login
A354902
a(n) = 2*n^2 - 6*n + 11 for n > 1 with a(0)=1 and a(1)=3.
2
1, 3, 7, 11, 19, 31, 47, 67, 91, 119, 151, 187, 227, 271, 319, 371, 427, 487, 551, 619, 691, 767, 847, 931, 1019, 1111, 1207, 1307, 1411, 1519, 1631, 1747, 1867, 1991, 2119, 2251, 2387, 2527, 2671, 2819, 2971, 3127, 3287, 3451, 3619, 3791, 3967, 4147, 4331, 4519, 4711, 4907
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
Lecture Notes for Computer Science 2530, Height-balanced trees
NIST, Root node
NIST, Leaf node
Wikipedia, Full binary tree
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
Sequence in context: A123080 A161387 A229086 * A022406 A355288 A132447
KEYWORD
nonn,easy
AUTHOR
Sumukh Patel, Jun 11 2022
STATUS
approved