Horton-Strahler numbers for binary butterfly trees: exact analysis

Helmut Prodinger · 2025

Read Horton-Strahler numbers for binary butterfly trees: exact analysis by Helmut Prodinger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18664.txt.

Introduction

Helmut Prodinger, writing alone, analyzes a number attached to a special family of trees. The trees, called binary butterfly trees, are formed by gluing two binary trees together in a particular way, which changes how likely each shape is. The number in question, the Horton-Strahler number, measures a tree's branching complexity and is a classic topic in combinatorics. Prodinger gives a thorough exact and asymptotic analysis, following a suggestion in a recent paper, and finds that in the long run these glued trees behave just like classical binary trees.

Catalog record

CREATORHelmut Prodinger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE14 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-18664

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Horton-Strahler numbers for binary butterfly trees: exact analysis Helmut Prodinger Abstract . Peca suggested in a recent paper on the arxiv to consider binary butterfly trees and their Horton-Strahler numbers. The trees are obtained by glueing two binary trees together in a special way; the results are again binary trees but with a different probability distribution. A thorough combinatorial analysis is provided and leads asymptotically to the same results as for classical binary trees. 2020 Mathematics Subject Classification 05A15 2020 Mathematics Subject Classification 05A15 1. Binary trees and Horton-Strahler numbers We start with some classical observations about binary trees and Horton-Strahler numbers (also called register function in Computer science). The pioneering papers are by Flajolet, Raoult, and Vuillemin [ 2 ] and Kemp [ 3 ] . The author has collected some material in [ 5 , 7 , 8 ] . Binary trees may be expressed by the following symbolic equation, which says that they include the empty tree and trees recursively built from a root followed by two subtrees (left and right), which are binary trees: \mathscr{B} = ∎ + \mathscr{B} \mathscr{B} Binary trees are counted by Catalan numbers and the parameter reg , (register function, Horton-Strahler numbers) is recursively defined by attaching the number 0 to the leaves, and then working our way up: if both subtrees are labelled with the same number, the root will get 1 + this number, otherwise the larger value of the subtrees bubbles up. The value at the root is then the parameter of interest. There is a recursive description of this function: \textsf{reg}(\square)=0 , and if tree t has subtrees t_{1} and t_{2} , then \textsf{reg}(t)=\begin{cases}\max\{\textsf{reg}(t_{1}),\textsf{reg}(t_{2})\}&\text{ if }\textsf{reg}(t_{1})\neq\textsf{reg}(t_{2}),\\ 1+\textsf{reg}(t_{1})&\text{ otherwise}.\end{cases} Here is an example: 2 1 2 0 1 1 1 0 0 0 0 0 0 Let \mathscr{R}_{p} denote the family of binary trees with Horton-Strahler number equal to p , then one gets immediately from the recursive definition: \mathscr{R}_{p} = \mathscr{R}_{p-1} \mathscr{R}_{p-1} + \mathscr{R}_{p} \sum\limits_{j<p}\mathscr{R}_{j} + \sum\limits_{j<p}\mathscr{R}_{j} \mathscr{R}_{p} In terms of generating functions, these equations are translated into R_{p}(z)=zR_{p-1}^{2}(z)+2zR_{p}(z)\sum_{j<p}R_{j}(z); the variable z is used to mark the size (i. e., the number of internal nodes) of the binary tree. See [ 7 ] ; compare also [ 8 ] . Flajolet et al. resp. Kemp were able to solve this explicitly! Nowadays, several strategies to do this are known; we only report the results as they will be used later in this paper. The substitution z=\frac{u}{(1+u)^{2}} that de Bruijn, Knuth, and Rice [ 1 ] also used, produces the nice expression R_{p}(z)=\frac{1-u^{2}}{u}\frac{u^{2^{p}}}{1-u^{2^{p+1}}}. The generating function S_{p}(z)=R_{p}+R_{p+1}+R_{p+2}+\cdots of binary trees with register function \geq p is equally important. One can check directly that \mathscr{S}_{p} = \mathscr{S}_{p-1} \mathscr{S}_{p-1} + \mathscr{S}_{p} \mathscr{B}\!\setminus\!S_{p-1} + \mathscr{B}\!\setminus\!S_{p-1} \mathscr{S}_{p} Hence \displaystyle S_{p}(z)=zS_{p-1}^{2}+zS_{p}(B-S_{p-1})+z(B-S_{p-1})S_{p}\quad p\geq 1,\quad S_{0}=B, and S_{p}(z)=\frac{1-u^{2}}{u}\frac{u^{2^{p}}}{1-u^{2^{p}}}. Peca [ 4 ] introduced a “butterfly” tree by glueing two binary trees together. The motivation came from binary search trees which are binary trees but with a different statistics underlying; binary search trees are equivalent to permutations and thus enumerated by n! , not by Catalan numbers. The interest was, however, in the Horton-Strahler numbers of the “butterfly” trees. The operation \oplus is first defined on permutations: The operation \pi_{1}\oplus\pi_{2} is defined like this: Both permutations are written in one-line notation in terms of 1,2,\dots ; then, the second permutation is lifted up by m , if m is the size of the permutation \pi_{1} ; with the resulting string of numbers, the final binary search tree is formed. A thorough analysis of the Horton-Strahler numbers in these butterfly trees was requested in [ 4 ] . This is the purpose of this paper. The resulting tree can be described without permutations by finding the rightmost leaf of t_{1} , and then replacing it by the tree t_{2} . Peca also considered a version of \ominus , but that is basically a symmetric version of \oplus , and we will not consider it further. The resulting object is again a binary tree, but one cannot reconstruct the two binary trees t_{1} and t_{2} from it. In order to do so, we consider the path from the root to the rightmost leaf, and consider exactly one edge as being distinguished (marked). From this, the reconstruction is possible. We avoid to consider the empty tree for t_{1} since the path of interest has no edges. The generating function of these marked binary trees is A:=(B-1)B=u(1+u) . The enumeration is as follows, since B is known: A=\frac{1-3z}{2z^{2}}-\frac{(1-z)\sqrt{1-4z}}{2z^{2}},\qquad[z^{n}]A(z)=\frac{3(2n)!}{(n-1)!(n+2)!},\ n\geq 1. \bullet \bullet \bullet \blacksquare \spadesuit \blacksquare \blacksquare \bullet \bullet \blacksquare \blacksquare \blacksquare \bullet \bullet \bullet \bullet \bullet \blacksquare \blacksquare \bullet \bullet \blacksquare \blacksquare \blacksquare Figure 1. Two binary trees t_{1} , t_{2} , the rightmost leaf of t_{1} indicated, and then t_{2} glued there, with resulting binary tree t_{1}\oplus t_{2} \bullet \bullet \bullet \bullet \bullet \blacksquare \blacksquare \bullet \bullet \blacksquare \blacksquare \blacksquare \bullet \bullet \bullet \bullet \bullet \blacksquare \blacksquare \bullet \bullet \blacksquare \blacksquare \blacksquare Figure 2. The resulting tree t_{1}\oplus t_{2} can originate in two possible ways from glueing two trees together. When we consider the elements of \mathscr{A} and ignore the marking of an edge on the rightmost path, we have a binary tree and thus can introduce the Horton-Strahler numbers on the elements of \mathscr{A} . No object has Horton-Strahler number equal to 0, and we introduce T_{p}(z) , the generating function of the elements of \mathscr{A} with Horton-Strahler number \geq p . We will find a recursion for T_{p} that is akin to the recursion for S_{p} and use the fact that S_{p} is explicitly known. This is similar to [ 6 ] where the author solved a problem left open by Yekutieli and Mandelbrot [ 9 ] , although the present situation is more involved. The further considerations deserve a section on its own. 2. Horton-Strahler numbers resulting from glueing together two binary trees Recall that \displaystyle S_{p}(z)=zS_{p-1}^{2}+zS_{p}(B-S_{p-1})+z(B-S_{p-1})S_{p},\quad p\geq 1. Using a similar reasoning, distinguishing whether the first right edge is marked (first line) or is not marked (second line), we find \displaystyle T_{p}(z) \displaystyle=zS_{p-1}^{2}+zS_{p}(B-S_{p-1})+z(B-S_{p-1})S_{p} \displaystyle+zS_{p-1}T_{p-1}+zS_{p}(A-T_{p-1})+z(B-S_{p-1})T_{p}, or \displaystyle T_{p}(z) \displaystyle=S_{p}+zS_{p-1}T_{p-1}+zS_{p}(A-T_{p-1})+z(B-S_{p-1})T_{p},\quad p\geq 2,\text{ and }T_{1}=A. Further \displaystyle T_{p}(z)\big(1-z(B-S_{p})\big) \displaystyle=S_{p}(1+zA)+zT_{p-1}(S_{p-1}-S_{p}). A direct computation yields \displaystyle 1-z(B-S_{p}) \displaystyle=\frac{1-u^{2^{p}+1}}{(1+u)(1-u^{2^{p}})},\quad 1+zA=\frac{1+u+u^{2}}{1+u}. Further \displaystyle S_{p-1}-S_{p}=R_{p-1}=\frac{1-u^{2}}{u}\frac{u^{2^{p-1}}}{1-u^{2^{p}}}. Some rearrangements lead to \displaystyle T_{p}(z)(1-u^{2^{p-1}+1})(1+u^{2^{p-1}}) \displaystyle=\frac{1-u^{2}}{u}u^{2^{p}}(1+u+u^{2})+T_{p-1}(1-u)u^{2^{p-1}}; this first order recursion will be solved by introduction of summation factors and eventually by summation. This will be done in a few steps; \displaystyle\frac{T_{p}(z)}{u^{2^{p}}}(1-u^{2^{p-1}+1})(1+u^{2^{p-1}}) \displaystyle=\frac{1-u^{2}}{u}(1+u+u^{2})+\frac{T_{p-1}(z)}{u^{2^{p-1}}}(1-u); \displaystyle\frac{T_{p}(z)}{u^{2^{p}}}(1-u^{2^{p-1}+1})\prod_{j=0}^{p-1}(1+u^{2^{j}}) \displaystyle=\frac{1-u^{2}}{u}(1+u+u^{2})\prod_{j=0}^{p-2}(1+u^{2^{j}}) \displaystyle+\frac{T_{p-1}(z)}{u^{2^{p-1}}}(1-u)\prod_{j=0}^{p-2}(1+u^{2^{j}}). Evaluating the products yields \displaystyle\frac{T_{p}(z)(1-u^{2^{p-1}+1})}{u^{2^{p}}}(1-u^{2^{p}}) \displaystyle=\frac{1-u^{2}}{u}(1+u+u^{2})(1-u^{2^{p-1}}) \displaystyle+\frac{T_{p-1}(z)(1-u^{2^{p-1}})}{u^{2^{p-1}}}(1-u) and \displaystyle\frac{T_{p}(z)(1-u^{2^{p}})}{u^{2^{p}}(1-u)^{p}}(1-u^{2^{p-1}+1}) \displaystyle=\frac{1-u^{2}}{u(1-u)^{p}}(1+u+u^{2})(1-u^{2^{p-1}}) \displaystyle+\frac{T_{p-1}(z)(1-u^{2^{p-1}})}{u^{2^{p-1}}(1-u)^{p-1}} Introducing a further product, \displaystyle\frac{T_{p}(z)(1-u^{2^{p}})}{u^{2^{p}}(1-u)^{p}}\prod_{j=0}^{p-1}(1-u^{2^{j}+1}) \displaystyle=\frac{1+u}{u(1-u)^{p-1}}(1+u+u^{2})(1-u^{2^{p-1}})\prod_{j=0}^{p-2}(1-u^{2^{j}+1}) \displaystyle+\frac{T_{p-1}(z)(1-u^{2^{p-1}})}{u^{2^{p-1}}(1-u)^{p-1}}\prod_{j=0}^{p-2}(1-u^{2^{j}+1}). An abbreviation is useful: \displaystyle\omega_{p}:=\frac{T_{p}(z)(1-u^{2^{p}})}{u^{2^{p}}(1-u)^{p}}\prod_{j=0}^{p-1}(1-u^{2^{j}+1}), then we get a form that can be summed: \displaystyle\omega_{p}=\omega_{p-1}+\frac{1+u}{u(1-u)^{p-1}}(1+u+u^{2})(1-u^{2^{p-1}})\prod_{j=0}^{p-2}(1-u^{2^{j}+1}) and so \displaystyle\omega_{p}=\omega_{1}+\sum_{h=1}^{p-1}\frac{1+u}{u(1-u)^{h}}(1+u+u^{2})(1-u^{2^{h}})\prod_{j=0}^{h-1}(1-u^{2^{j}+1}). Coming back to the original quantities T_{p}(z) , \displaystyle T_{p}(z) \displaystyle=\omega_{p}\frac{u^{2^{p}}(1-u)^{p}}{(1-u^{2^{p}})}\bigg/\prod_{j=0}^{p-1}(1-u^{2^{j}+1}) \displaystyle=\bigg[(1+u)^{2}+(1+u+u^{2})\sum_{h=1}^{p-1}\frac{1-u^{2^{h}}}{1-u}\prod_{j=0}^{h-1}\frac{1-u^{2^{j}+1}}{1-u}\bigg] \displaystyle\qquad\times\frac{1-u^{2}}{u}\frac{u^{2^{p}}}{1-u^{2^{p}}}\prod_{j=0}^{p-1}\frac{1-u}{1-u^{2^{j}+1}}. Note that \dfrac{1-u^{2}}{u}\dfrac{u^{2^{p}}}{1-u^{2^{p}}}=S_{p}(z) . Theorem 1 . The generating function T_{p}(z) of trees in \mathscr{A} with Horton-Strahler number \geq p is for p\geq 0 given by \displaystyle T_{p}(z)=S_{p}(z)\bigg[(1+u)^{2}+(1+u+u^{2})\sum_{h=1}^{p-1}\frac{1-u^{2^{h}}}{1-u}\prod_{j=0}^{h-1}\frac{1-u^{2^{j}+1}}{1-u}\bigg]\prod_{j=0}^{p-1}\frac{1-u}{1-u^{2^{j}+1}}. Note that this formula has been tested. Since the generating function is fully explicit one has (in principle) access to the coefficients, i. e., to the numbers of binary butterfly trees of a given number of nodes and a given Horton-Strahler number. 3. The average value of Horton-Strahler numbers in marked binary trees By general

Read the complete text