Extremal ranks of unlabeled multifurcating rooted trees in a bijective encoding by the positive integers

Maranca and Rosenberg (2024) devised a ranking scheme for unlabeled multifurcating rooted trees, in which the trees are bijectively associated with the positive integers. Here, generalizing earlier results for bifurcating trees, we determine, for trees with a fixed number of leaves, which multifurcating trees obtain the maximal and minimal ranks. We identify these maximizing and minimizing trees for each of two sets of unlabeled multifurcating rooted trees: strictly $k$-furcating trees, in which each internal node possesses exactly $k$ descendants, and at-most-$k$-furcating trees, in which internal nodes possess at least 2 and at most $k$ descendants. In both scenarios, we find that a tree that can be regarded as maximally balanced attains the minimal rank, and a minimally balanced tree attains the maximal rank. We deduce recurrences for the maximal and minimal rank for trees with fixed numbers of leaves in both the strictly $k$-furcating and at-most-$k$-furcating cases. The maximal rank on $(n-1)(k-1)+1$ leaves grows with $(k!{)}^{\frac{1}{k-1}}{\beta }_k^{(k^n)}$ in the strictly $k$-furcating case, and the maximal rank on $n$ leaves grows with $(k!{)}^{\frac{1}{k-1}}{\gamma }_k^{(k^n)}$ in the at-most-$k$-furcating case, where ${\beta }_k>1$ and ${\gamma }_k>1$ are constants that depend on the value of $k$. We show that ${\beta }_k$ decreases as the value of $k$ increases, and that ${\gamma }_k>{\beta }_k$ for $k\ge 3$. The results contribute to the use of tree encodings for empirical characterization of phylogenies and measurement of tree balance.