Sumukh Patel - cp's OEIS frontend

User: Sumukh Patel

Sumukh Patel has authored 2 sequences.

A355288 a(0)=1, a(1)=3, a(2)=7; thereafter a(n) = a(n-1) + a(n-2) + 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

Sumukh Patel, Jun 27 2022

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

			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

Sumukh Patel, Table of n, a(n) for n = 0..1000
Lecture Notes for Computer Science 2530, Height-balanced trees
NIST, Root node
Wikipedia, Full binary tree
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A354902.

[n eq 0 select 1 else 4*Fibonacci(n+1) - 1: n in [0..40]];

Join[{1},Table[4*Fibonacci[n + 1] - 1, {n, 1, 40}]]

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.

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

Original entry on oeis.org

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

Sumukh Patel, Jun 11 2022

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.

			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

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

Cf. A022856, A027688.

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

CoefficientList[Series[(1 + x^2 - 2 x^3 + 4 x^4)/(1 - x)^3, {x, 0, 51}], x] (* Michael De Vlieger, Jun 19 2022 *)

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

cp's OEIS Frontend

User: Sumukh Patel

A355288 a(0)=1, a(1)=3, a(2)=7; thereafter a(n) = a(n-1) + a(n-2) + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Mathematica

Formula

cp's OEIS Frontend

User: Sumukh Patel

A355288 a(0)=1, a(1)=3, a(2)=7; thereafter a(n) = a(n-1) + a(n-2) + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Mathematica

Formula

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