login
A355288
a(0)=1, a(1)=3, a(2)=7; thereafter a(n) = a(n-1) + a(n-2) + 1.
1
1, 3, 7, 11, 19, 31, 51, 83, 135, 219, 355, 575, 931, 1507, 2439, 3947, 6387, 10335, 16723, 27059, 43783, 70843, 114627, 185471, 300099, 485571, 785671, 1271243, 2056915, 3328159, 5385075, 8713235, 14098311, 22811547, 36909859, 59721407, 96631267, 156352675, 252983943, 409336619, 662320563
OFFSET
0,2
COMMENTS
a(n) is the minimum number of nodes required for a full binary tree of height n with every node height-balanced, and the root node has a balance factor of 0.
Full binary tree: A binary tree is called a full binary tree if each node has exactly two or no children.
Essentially the same as A022403. - R. J. Mathar, Sep 23 2022
LINKS
Lecture Notes for Computer Science 2530, Height-balanced trees
NIST, Root node
Wikipedia, Full binary tree
FORMULA
a(0)=1, a(1)=3, a(2)=7; thereafter a(n) = a(n-1) + a(n-2) + 1.
From Stefano Spezia, Jun 27 2022: (Start)
G.f.: (1 + x + x^2 - 2*x^3)/((1 - x)*(1 - x - x^2)).
a(n) = 2*a(n-1) - a(n-3) for n > 3.
a(n) = 2^(1-n)*((1 + sqrt(5))^(n+1) - (1 - sqrt(5))^(n+1))/sqrt(5) - 1 for n > 0.
E.g.f.: 4*exp(x/2)*(5*cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x) - 2. (End)
a(n) = 4*A000045(n+1) - 1, for n >= 1.
a(n) = 2*A001595(n) + 1, for n >= 1.
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 o N N
/ \ / \
N N N N
MATHEMATICA
Join[{1}, Table[4*Fibonacci[n + 1] - 1, {n, 1, 40}]]
PROG
(Magma) [n eq 0 select 1 else 4*Fibonacci(n+1) - 1: n in [0..40]];
CROSSREFS
Cf. A354902.
Sequence in context: A229086 A354902 A022406 * A132447 A132449 A132453
KEYWORD
nonn,easy
AUTHOR
Sumukh Patel, Jun 27 2022
STATUS
approved