A354902 a(n) = 2*n^2 - 6*n + 11 for n > 1 with a(0)=1 and a(1)=3.

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

Author

Sumukh Patel, Jun 11 2022

Keywords

• nonn
• easy

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.

Examples

			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
		

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).

Crossrefs

Cf. A022856, A027688.

Programs

C

int a(int n){ return n>1 ? 2*(n*n) - 6*n + 11 : 2*n + 1; }

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 *)

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