Refined Horton-Strahler numbers I: a discrete bijection

The Horton-Strahler number of a rooted tree T is the height of the tallest complete binary tree that can be homeomorphically embedded in T. The number of full binary trees with n internal vertices and Horton-Strahler number s is known to be the same as the number of Dyck paths of length $2n$ whose height h satisfies log₂(1+h)=s. In this paper, we present a new bijective proof of the above result, that in fact strengthens and refines it as follows. We introduce a sequence of trees (τᵢ,i ≥ 0) which "interpolates" the complete binary trees, in the sense that τ2ʰ-1 is the complete binary tree of height h for all h ≥ 0, and τᵢ₊₁ strictly contains τᵢ for all i ≥ 0. Defining S(T) to be the largest i for which τᵢ can be homeomorphically embedded in T, we then show that the number of full binary trees T with n internal vertices and with S(T)=h is the same as the number of Dyck paths of length $2n$ with height h. (We call S(T) the refined Horton-Strahler number of T.) Our proof is bijective and relies on a recursive decomposition of binary trees (resp. Dyck paths) into subtrees with strictly smaller refined Horton-Strahler number (resp. subpaths with strictly smaller height). In a subsequent paper, we will show that the bijection has a continuum analogue, which transforms a Brownian continuum random tree into a Brownian excursion and under which (a continuous analogue of) the refined Horton-Strahler number of the tree becomes the height of the excursion.