Construction and Composition of Rooted Trees via Descent Functions

We propose a novel approach for studying rooted trees by using functions that we will call descent functions. We provide a construction method for rooted trees that allows to study their properties through the use of descent functions. Moreover, in this way, we are able to compose rooted trees with each other. Such a new composition of rooted trees is a very powerful tool applied in this paper in order to obtain important results as the creation of new rational and Pythagorean trees. 1. Introduction Trees represent one of the most important topics in the combinatorial theory. Generating trees whose nodes are elements of a structure may constitute an important step for studying the properties of the structure itself and for the structure visualization. In this paper, some structural properties of trees will be dealt in a novel way in order to make easy the tree generation for sets satisfying specific requirements. One of the main subjects of the present work is the so-called descent functions. Identifying functions of this type allows to reveal a simple and direct technique to the generation of trees on sets equipped with a weight function over a partially ordered set. Furthermore, the introduced technique yields to a substantial simplification of the study of tree levels and easily and directly finds the degree of any node. Moreover, we introduce a composition of trees, which represents a completely new and very powerful tool for the generation of trees. This operation gives the feasibility of generating a new tree starting from a given pair of trees associated with a generating system once we assign a partition of the system itself. We present some examples to show the power of this tool. In particular, the composition of trees will be used to construct new examples of trees of rational numbers (rational trees) and of trees of primitive Pythagorean triples (Pythagorean trees). These applications are of special interest because nowadays only three examples of the first type [1–4] and two of the latter are known [5–7]. On the other hand, one can observe that the used techniques allow to generate an infinite number of trees of either type, and that the shown applications are merely representative. The techniques of explicit construction of the trees described here show some features that arise from properties of the algebraic elements involved, making themselves natural and rigorous. 2. Tree Construction via Descent Functions In this section, we present a new and useful approach to rooted trees by using particular functions that we will call descent