OFFSET
1,5
COMMENTS
The rooted binary echelon tree plays an important role in the literature on tree balance, and the Colless index is an established balance measure. The n-th value of the sequence gives the values of the Colless index for the rooted binary echelon tree with n leaves.
Let T be the rooted binary echelon tree with n leaves, which can be constructed recursively as follows: Let k=floor(log_2(n)). If n==2^k, the rooted binary echelon tree T equals the fully balanced tree with 2^k leaves. If n>2^k, then T=(T_b,T_c), where T_b is the fully balanced tree of size 2^k and T_c is the echelon tree of size n-2^k.
The Colless index of a tree is defined as: C(T)=Sum_{v: inner vertex of T} |l_b-l_c|, where l_b is the number of leaves descending from the left child of v and l_c is the number of leaves descending from the right child of v (or vice versa).
Now, a(n) is the Colless index of the rooted binary echelon tree with n leaves.
LINKS
Mareike Fischer, Lina Herbst, Sophie Kersting, Annemarie Luise Kühn, and Kristina Wicke, Tree Balance Indices: A comprehensive survey, Springer Nature Link, 2023.
Linda Knüver and Mareike Fischer, Revealing the building blocks of tree balance: fundamental units of the Sackin and Colless Indices, arXiv:2509.04995 [q-bio.PE], 2025-2026.
FORMULA
a(2^n)=0 for n>=0, otherwise a(n) = 2*m - n + a(n-m) where m=2^k is the highest power of 2 <= n. - Sean A. Irvine, Jul 16 2026
EXAMPLE
a(1) = 0 as the rooted binary echelon tree T with 1 leaf consists only of one vertex, which is a leaf, so the Colless index is a summation over an empty sum and thus equals 0.
a(2) = 0 as the rooted binary echelon tree T with 2 leaves consists only of a so-called "cherry"; i.e., two leaves attached to a common inner vertex of T, so the Colless index is 1-1=0.
a(3) = 1 as the rooted binary echelon tree with 3 leaves consists of the root of the tree, whose children are a cherry and a singleton leaf. The cherry parent has Colless value 1-1=0, and the root of the entire tree has Colless value 2-1=1, giving a Colless index of 0+1=1 for the entire tree.
MAPLE
a:= proc(n) option remember;
(m-> `if`(m=n, 0, 2*m-n+a(n-m)))(2^ilog2(n))
end:
seq(a(n), n=1..72); # Alois P. Heinz, Jul 17 2026
MATHEMATICA
CollessIndex[tree_] := Module[{list, size1, size2},
list = Level[tree, {0, Infinity}];
list = DeleteCases[list, 1];
Sum[
size1 = Total[element[[1]], Infinity];
size2 = Total[element[[2]], Infinity];
Abs[size1 - size2]
, {element, list}]
];
MBtree[1] = 1;
MBtree[n_] := {MBtree[Ceiling[n/2]], MBtree[Floor[n/2]]};
EchelonTree[1] = 1;
EchelonTree[n_] := Module[{kn = Ceiling[Log2[n]]},
{MBtree[2^(kn - 1)], EchelonTree[n - 2^(kn - 1)]}
];
Table[CollessIndex[EchelonTree[n]], {n, 72}]
CROSSREFS
KEYWORD
nonn,new
AUTHOR
Mareike Fischer, Jul 04 2026
STATUS
approved