A279521 Maximum number of single-direction edges in leveled binary trees with n nodes.
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
Offset: 1
Keywords
Examples
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.
Links
- Adrijan Božinovski, Table of n, a(n) for n = 1..10000
- Stevo Bozinovski and Adrijan Bozinovski, Brain Rhythms, Pascal Triangle, and Brain-Computer Interface, ICEST (Ohrid, North Macedonia 2019), 191-193.
- NIST, Height-balanced tree
- NIST, Complete binary tree
- NIST, Full binary tree
Programs
-
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, h-1); 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; } -
Maple
a:= n-> (g-> min(g-1, n-g/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^(h-1) - 1) + (-1) ^ Boole[# >= 0] # &@ (-n + 3*2^(h-1) - 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 *) -
Python
class A279521(): @staticmethod def _heaviside(x): return 1 if x >= 0 else 0 @staticmethod def at(n): h = n.bit_length() -1 p2h = 2**h p2h_1 = 2**(h-1) hs = A279521._heaviside(-n + 3 * p2h_1 - 1) return ((n + p2h_1 - 1) * hs + (-1)**hs * (p2h - 1)) print([A279521.at(n) for n in range(1,100)]) # George Tanev, Jan 01 2017, indentation R. J. Mathar, Mar 29 2023
-
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
Formula
a(n) = (n + 2^(h-1) - 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^(h-1) - 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 n-1 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., non-leaf) 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 h-1 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^(h-1) - 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^(h-1), 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^(h-1) - 1. Therefore, the number of strictly right edges will keep increasing until n < 2^h - 1 + 2^(h-1), i.e., n < 3*2^(h-1) - 1, or, stated differently, -n + 3*2^(h-1) - 1 > 0. This condition can be expressed with the Heaviside step function as He = H(-n + 3*2^(h-1) - 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^(h-1) - 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^(h-1) - 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 h-1 (the level before the last in the leveled binary tree) is 2^(h-1) - 1, the number of edges in the leveled binary tree of level h will be n - 1 - (2^(h-1) - 1) = n - 2^(h-1), as long as He = 1. Since the leveled tree will be filled with right child nodes (and thus right edges) first, n - 2^(h-1) 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^(h-1) for He = 1. The case for He = 1 can be expressed as n - 2^(h-1) = n + 2^(h-1) - 2^h = n + 2^(h-1) - 1 - 2^h + 1 = n + 2^(h-1) - 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^(h-1) - 1)*He + (-1)^He * (2^h - 1), which is the formula for a(n).
For k > 0 we have: a(2k) = 1 + a(k-1) + 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
a(n) = A006165(n+1) - 1. - Alois P. Heinz, Feb 03 2024
Comments