Tree Height and the Asymptotic Mean of the Colijn-Plazzotta Rank of Unlabeled Binary Rooted Trees

The Colijn-Plazzotta ranking is a bijective encoding of the unlabeled binary rooted trees with positive integers. We show that the rank f(t) of a tree t is closely related to its height h, the maximal path length from a leaf to the root. We consider the rank $f\left({\tau }_n\right)$ of a random n-leaf tree ${\tau }_n$ under each of three models: (i) uniformly random unlabeled unordered binary rooted trees, or unlabeled topologies; (ii) uniformly random leaf-labeled binary trees, or labeled topologies under the uniform model; and (iii) random binary search trees, or labeled topologies under the Yule-Harding model. Relying on the close relationship between tree rank and tree height, we obtain results concerning the asymptotic properties of $loglogf\left({\tau }_n\right)$ . In particular, we find $E\{{log}_{2}logf\left({\tau }_n\right)\}\sim 2\sqrt{\pi n}$ for uniformly random unlabeled ordered binary rooted trees and uniformly random leaf-labeled binary trees, and for a constant $\alpha \approx 4.31107$ , $E\{{log}_{2}logf\left({\tau }_n\right)\}\sim \alpha logn$ for leaf-labeled binary trees under the Yule-Harding model. We show that the mean of $f\left({\tau }_n\right)$ itself under the three models is largely determined by the rank $c_{n-1}$ of the highest-ranked tree-the caterpillar-obtaining an asymptotic relationship with ${\pi }_n{c}_{n-1}$ , where ${\pi }_n$ is a model-specific function of n. The results resolve open problems, providing a new class of results on an encoding useful in mathematical phylogenetics.