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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:msub><mml:mi>τ</mml:mi> <mml:mi>n</mml:mi></mml:msub> <mml:mo>)</mml:mo></mml:mrow> </mml:math> of a random n-leaf tree <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>τ</mml:mi> <mml:mi>n</mml:mi></mml:msub> </mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:msub><mml:mi>τ</mml:mi> <mml:mi>n</mml:mi></mml:msub> <mml:mo>)</mml:mo></mml:mrow> </mml:math> . In particular, we find <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>E</mml:mi> <mml:mrow><mml:mo>{</mml:mo> <mml:msub><mml:mo>log</mml:mo> <mml:mn>2</mml:mn></mml:msub> <mml:mo>log</mml:mo> <mml:mi>f</mml:mi> <mml:mrow><mml:mo>(</mml:mo> <mml:msub><mml:mi>τ</mml:mi> <mml:mi>n</mml:mi></mml:msub> <mml:mo>)</mml:mo></mml:mrow> <mml:mo>}</mml:mo></mml:mrow> <mml:mo>∼</mml:mo> <mml:mn>2</mml:mn> <mml:msqrt><mml:mrow><mml:mi>π</mml:mi> <mml:mi>n</mml:mi></mml:mrow> </mml:msqrt> </mml:mrow> </mml:math> for uniformly random unlabeled ordered binary rooted trees and uniformly random leaf-labeled binary trees, and for a constant <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>α</mml:mi> <mml:mo>≈</mml:mo> <mml:mn>4.31107</mml:mn></mml:mrow> </mml:math> , <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>E</mml:mi> <mml:mo>{</mml:mo> <mml:msub><mml:mo>log</mml:mo> <mml:mn>2</mml:mn></mml:msub> <mml:mo>log</mml:mo> <mml:mi>f</mml:mi> <mml:mrow><mml:mo>(</mml:mo> <mml:msub><mml:mi>τ</mml:mi> <mml:mi>n</mml:mi></mml:msub> <mml:mo>)</mml:mo></mml:mrow> <mml:mo>}</mml:mo> <mml:mo>∼</mml:mo> <mml:mi>α</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi></mml:mrow> </mml:math> for leaf-labeled binary trees under the Yule-Harding model. We show that the mean of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:msub><mml:mi>τ</mml:mi> <mml:mi>n</mml:mi></mml:msub> <mml:mo>)</mml:mo></mml:mrow> </mml:math> itself under the three models is largely determined by the rank <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>c</mml:mi> <mml:mrow><mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn></mml:mrow> </mml:msub> </mml:math> of the highest-ranked tree-the caterpillar-obtaining an asymptotic relationship with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow><mml:msub><mml:mi>π</mml:mi> <mml:mi>n</mml:mi></mml:msub> <mml:msub><mml:mi>c</mml:mi> <mml:mrow><mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn></mml:mrow> </mml:msub> </mml:mrow> </mml:math> , where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>π</mml:mi> <mml:mi>n</mml:mi></mml:msub> </mml:math> 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.