

A279521


Maximum number of singledirection edges in leveled binary trees with n nodes.


2



0, 1, 1, 2, 3, 3, 3, 4, 5, 6, 7, 7, 7, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 33, 34, 35, 36, 37, 38
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

A leveled binary tree is a binary tree where every level, except possibly the last, is completely filled.
Unlike a complete binary tree, where nodes in the last level are always stacked linearly from left to right, insertion in a leveled binary tree can be done in any order.
The formula for this integer sequence determines the maximum number of singledirection edges in a leveled binary tree of an arbitrary size n, and is presented alongside its proof. The same formula gives the maximum number of right, as well as the maximum number of left, edges in any leveled binary tree. The proof is analogous for both cases.
This sequence also gives the number of different nonordered neighboring pairs in the SternBrocot sequence A002487.  Horst H. Manninger, Jun 10 2021


LINKS

Adrijan Božinovski, Table of n, a(n) for n = 1..10000
Stevo Bozinovski and Adrijan Bozinovski, Brain Rhythms, Pascal Triangle, and BrainComputer Interface, ICEST (Ohrid, North Macedonia 2019), 191193.
NIST, Heightbalanced tree
NIST, Complete binary tree
NIST, Full binary tree


FORMULA

a(n) = (n + 2^(h1)  1)*He + (1)^He * (2^h  1), where h = floor(log_2(n)) and is the height of the binary tree, He = H(n + 3*2^(h1)  1) and H is the Heaviside step function (i.e., H(x) = 1 if x >= 0 and H(x) = 0 if x < 0).
Proof:
If n = 2^k  1 (for any k > 0), i.e., if n = {3, 7, 15, ...}, the binary tree is full, and, as any tree, contains n1 edges (1 fewer than the number of nodes). Any n = 2^k  1 is an odd number, so the number one less than that is always even. In a full binary tree, every internal (i.e., nonleaf) node has both a left and a right child node, so there will be equally as many right as left edges in such a tree. Thus, half of that number will be the number of strictly right or strictly left edges. In this proof, strictly right edges will be viewed (the proof is analogous for strictly left edges).
If n != 2^k  1, the leveled binary tree is not full. More precisely, the last level (level h) isn't full, but the subtree consisting of the root and all the levels of the tree up to (and including) level h1 is. As in one of the examples, the leveled tree with n = 8 is not full and has a height of h = 3, but its subtree up to and including level h = 2 is full. 2^h  1 nodes will form the full subtree, which will have 2^h  2 edges, and half of those edges, i.e., 2^(h1)  1, will be strictly right.
The last level of the leveled binary tree can contain at most 2^h nodes. If it is filled with right child nodes first, the number of right edges will increase, up to a point when all of the right child nodes have been inserted and the next node to be inserted will have to be a left child node. As is evident in the given examples, it is possible to insert right child nodes in the last level of the leveled binary trees with n = 4 and n = 5, but in a leveled binary tree with n = 6 a left child node must be inserted in the last level (h = 2), since there is no more room to insert right child nodes. This forces a stop in the increase of the number of right edges. It can be observed that the moment when the number of right edges in a leveled binary tree must stop increasing is when a node is entered after half of the possible positions to insert nodes in the last level, i.e., 2^h / 2 = 2^(h1), have been occupied. The number of nodes in the leveled binary tree must be smaller than the number of nodes already present in the previous levels of the tree plus half of the nodes in the last level, in order for the maximum number of right edges to increase; otherwise the maximum number of right edges will remain 2^(h1)  1. Therefore, the number of strictly right edges will keep increasing until n < 2^h  1 + 2^(h1), i.e., n < 3*2^(h1)  1, or, stated differently, n + 3*2^(h1)  1 > 0. This condition can be expressed with the Heaviside step function as He = H(n + 3*2^(h1)  1).
There are two cases to consider:
1) When half of the nodes of the last level of the binary tree have been entered (i.e., it holds that He = H(n + 3*2^(h1)  1) = 0), the number of right edges reaches the maximum and it remains constant until the next level starts being filled. This maximum number is 2^h  1, i.e., the number of strictly right edges of a leveled binary tree of level h+1.
2) While the condition He = H(n + 3*2^(h1)  1) = 1 (i.e., is true), it is possible to insert right child nodes in the last level of the binary tree, thus there are less than half of the possible 2^h nodes in the last level inserted. Since the number of edges in a tree is always one less than the number of nodes, and since the number of nodes in the full binary tree of level h1 (the level before the last in the leveled binary tree) is 2^(h1)  1, the number of edges in the leveled binary tree of level h will be n  1  (2^(h1)  1) = n  2^(h1), as long as He = 1. Since the leveled tree will be filled with right child nodes (and thus right edges) first, n  2^(h1) will be the number of strictly right edges in a leveled binary tree of level h while half of the possible right child nodes in the last level have not been completely filled.
Therefore, the formula will be 2^h  1 for He = 0 and n  2^(h1) for He = 1. The case for He = 1 can be expressed as n  2^(h1) = n + 2^(h1)  2^h = n + 2^(h1)  1  2^h + 1 = n + 2^(h1)  1  (2^h  1), meaning that the case for He = 1 contains the case for He = 0. Both cases can be represented with a single expression as (n + 2^(h1)  1)*He + (1)^He * (2^h  1), which is the formula for a(n).
For k > 0 we have: a(2k) = 1 + a(k1) + a(k); a(2k+1) = 1 + 2*a(k).  Orson R. L. Peters, Aug 09 2019
a(n) = n  1  A277267(n).  Alois P. Heinz, Nov 16 2020


EXAMPLE

In a leveled binary tree with 1 node, there are at most 0 strictly right edges: n=1 => a(n)=0.
. o
In a leveled binary tree with 2 nodes, there are at most 1 strictly right edges: n=2 => a(n)=1.
. o
. \ <=
. o
In a leveled binary tree with 3 nodes, there are at most 1 strictly right edges: n=3 => a(n)=1.
. o
. / \ <=
. o o
In a leveled binary tree with 4 nodes, there are at most 2 strictly right edges: n=4 => a(n)=2.
. o
. / \ <=
. o o
. \ <=
. o
In a leveled binary tree with 5 nodes, there are at most 3 strictly right edges: n=5 => a(n)=3.
. o___
. / \ <=
. o o
. \ <= \ <=
. o o
In a leveled binary tree with 6 nodes, there are at most 3 strictly right edges: n=6 => a(n)=3.
. ___o___
. / \ <=
. o o
. / \ <= \ <=
. o o o
In a leveled binary tree with 7 nodes, there are at most 3 strictly right edges: n=7 => a(n)=3.
. ___o___
. / \ <=
. o o
. / \ <= / \ <=
. o o o o
In a leveled binary tree with 8 nodes, there are at most 4 strictly right edges: n=8 => a(n)=4.
. ___o___
. / \ <=
. __o o
. / \ <= / \ <=
. o o o o
. \ <=
. o
In a leveled binary tree with 9 nodes, there are at most 5 strictly right edges: n=9 => a(n)=5.
. ___o___
. / \ <=
. __o o
. / \ <= / \ <=
. o o o o
. \ <= \ <=
. o o
And so on.


MAPLE

a:= n> (g> min(g1, ng/2))(2^ilog2(n)):
seq(a(n), n=1..100); # Alois P. Heinz, Nov 16 2020


MATHEMATICA

Table[Function[h, n + 2^(h  1)  1 * Boole[# >= 0] # &@ (n + 3*2^(h1)  1) + (1) ^ Boole[# >= 0] # &@ (n + 3*2^(h1)  1) * (2^h  1)]@ Floor[Log2@ n], {n, 71}] (* George Tanev, Jan 01 2017 *)
a[0] = 0; a[1] = 1; lis = {}; m = 70; t = Flatten[Table[{a[2*n] = a[n], a[2*n + 1] = a[n] + a[n + 1]}, {n, m}]];
For[g = 2, g < m, g++, AppendTo[lis, Length[Sort[DeleteDuplicates[Sort[#] & /@ (Partition[t[[1 ;; g]], 2, 1])]]]]]
lis (* Horst H. Manninger, Jun 10 2021 *)


PROG

(Java)
static int a(int n)
{
int h = (int) Math.floor(Math.log(n) / Math.log(2));
int p2h = (int) Math.pow(2, h);
int p2h_1 = (int) Math.pow(2, h1);
int He = Heaviside(n + 3*p2h_1  1);
return (int) ((n + p2h_1  1)*He + Math.pow(1, He)*(p2h  1));
}
static int Heaviside(double x)
{
return x >= 0 ? 1 : 0;
}
(Scala)
def a(n: Int): Int = {
val h = Math.floor(Math.log(n) / Math.log(2)).toInt
val p2h = Math.pow(2, h).toInt
val p2h_1 = Math.pow(2, h  1).toInt
val hs = heaviside(n + 3 * p2h_1  1)
((n + p2h_1  1) * hs + Math.pow(1, hs) * (p2h  1)).toInt
}
/** George Tanev, Jan 01 2017 */
def heaviside(x: Double): Int = if (x >= 0) 1 else 0
(Python)
class Max(object):
def a(n):
h = math.floor(math.log(n) / math.log(2))
p2h = math.pow(2, h)
p2h_1 = math.pow(2, h  1)
hs = Max.heaviside(n + 3 * p2h_1  1)
return ((n + p2h_1  1) * hs + math.pow(1, hs) * (p2h  1))
a = staticmethod(a)
def heaviside(x):
return 1 if x >= 0 else 0
heaviside = staticmethod(heaviside)
# George Tanev, Jan 01 2017


CROSSREFS

Cf. A002487, A056971, A277267, A002487.
Essentially partial sums of A086694.
Sequence in context: A211535 A029069 A266341 * A076896 A275890 A029087
Adjacent sequences: A279518 A279519 A279520 * A279522 A279523 A279524


KEYWORD

nonn


AUTHOR

Adrijan Božinovski, Dec 14 2016


STATUS

approved



