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

Colijn & Plazzotta (Syst. Biol. 67:113-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 ₁, k ₂), k ₁ ⩾ k ₂ ⩾ 1, is then associated with the tree whose left subtree has rank k ₁ and whose right subtree has rank k ₂. Following dictionary order on ordered pairs, the tree whose left and right subtrees have the ordered pair of ranks (k ₁, k ₂) is assigned rank k ₁(k ₁ - 1)/2 + 1 + k ₂. With this ranking, given a number of leaves n, we determine recursions for a , the smallest rank assigned to some tree with n leaves, and b , the largest rank assigned to some tree with n leaves. The smallest rank a is assigned to the maximally balanced tree, and the largest rank b is assigned to the caterpillar. For n equal to a power of 2, the value of a is seen to increase exponentially with 2α for a constant α ≈ 1.24602; more generally, we show it is bounded a < 1.5 . The value of b is seen to increase with $$ for a constant β ≈ 1.05653. The great difference in the rates of increase for a and b 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.