On the Colijn-Plazzotta numbering scheme for unlabeled binary rooted trees.

ABSTRACT

Colijn & Plazzotta (Syst. Biol. 67113-126, 2018) introduced a scheme for bijectively associating the unlabeled binary rooted trees with the positive integers. First, the rank 1 is associated with the 1-leaf tree. Proceeding recursively, ordered pair (k 1, k 2), k 1 ⩾ k 2 ⩾ 1, is then associated with the tree whose left subtree has rank k 1 and whose right subtree has rank k 2. Following dictionary order on ordered pairs, the tree whose left and right subtrees have the ordered pair of ranks (k 1, k 2) is assigned rank k 1(k 1 - 1)/2 + 1 + k 2. With this ranking, given a number of leaves n, we determine recursions for a n , the smallest rank assigned to some tree with n leaves, and b n , the largest rank assigned to some tree with n leaves. The smallest rank a n is assigned to the maximally balanced tree, and the largest rank b n is assigned to the caterpillar. For n equal to a power of 2, the value of a n is seen to increase exponentially with 2α n for a constant α ≈ 1.24602; more generally, we show it is bounded a n < 1.5 n . The value of b n is seen to increase with 2 ß ( 2 n ) for a constant ß ≈ 1.05653. The great difference in the rates of increase for a n and b n indicates that as the index v is incremented, the number of leaves for the tree associated with rank v quickly traverses a wide range of values. We interpret the results in relation to applications in evolutionary biology.