# Construction and Composition of Rooted Trees via Descent Functions

Authors: Marco Abrate; Stefano Barbero; Umberto Cerruti; Nadir Murru
Journal: Algebra
 (2013)

---

## Abstract

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.


---

## Body

## 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-calleddescent 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 acomposition 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 calldescent functions. Let us start from the following.Definition 1.
A weight function overX is a function w:X→Y, for any set X and Y, such that  (1)
Yis a partially ordered set, where < is the relation of strict total order;(2)
∃ϵ∈X:w(ϵ)<w(x),forallx≠ϵ∈X;(3)
there are no infinite sequences(xi)i=0∞, with xi∈X, such that foralli, w(xi)>w(xi+1).It is easy to see that the elementϵ is unique. Moreover, if Y satisfies the descending chain condition for sets, then condition (3) is immediately verified.Definition 2.
Given a weight functionw over X, a descent function is a function θ:X*→X, where X*=X-{ϵ}, such that
(1)w(θ(x))<w(x),∀x∈X*.In this way, for allx∈X*, there exists an integer n such that θn(x)=ϵ (where θn=θ∘⋯∘θ︸n). This is sufficient to use the functions w and θ for generating rooted trees.Let us denote by𝒯 a rooted tree and by 𝒯m its mth level (𝒯0 contains only the root). We say that two nodes a and b are connected if and only if θ(a)=b or θ(b)=a. If θ(a)=b, then b is a child node whose parent node is a.Definition 3.
Given a rooted tree𝒯, the level of a node a is the natural number m such that a∈𝒯m.The tree structure of𝒯 is then completely determined by the descent function θ, by means of
(2)𝒯m={θ(x):∀x∈𝒯m+1}
and vice versa one has the following:
(3)𝒯m+1={θ-1(x):∀x∈𝒯m}.
Thus, a node a in 𝒯 belongs to the mth level if and only if θm(a)=ϵ and ϵ is the root.Definition 4.
We call descent tree a tree associated with a descent functionθ over a set X, as aforementioned, having weight function w over Y. The structure (X,Y,w,θ) is the generative tree system.Remark 5.
The nodes of rooted trees studied in this paper are labeled by the choice of the setX; that is, one and only one element of X corresponds to each node of the tree. However, we will not refer in this case to the term label because in the following, we use such a term in order to classify the nodes in some classes.Example 6.
Let us consider the following weight and descent functions:(4)w:ℕ0⟶ℕ0,w(n)=n,θ:ℕ0∖{1}⟶ℕ0,θ(n)=n2,neven,θ(n)=n-1,nodd.
It is straightforward to see that w and θ satisfy Definitions 1 and 2, respectively, for X=Y=ℕ and ϵ=1. Observing that
(5)θ-1(n)={n+1,2n},neven,θ-1(n)={2n},nodd,
starting from the root 1, it is easy to construct the tree, represented up to the 4th level in Figure 1.Figure 1Example 7.
LetX be the set of vectors (a1,…,at) such that t≥1, ai∈ℕ0 for every i, and a1≥a2≥⋯≥at. Moreover, let us consider Y=ℕ and the weight function w:X→Y defined by
(6)w(a1,…,at)=t+∑i=1t‍ai.
And thus ϵ=(1). Let us use the following descent function:
(7)θ(a1,…,at)=(a1,…,at-1),ifat=1,θ(a1,…,at)=(a1,…,at-1,at-1),ifat>1,
whose inverse is
(8)θ-1(a1,…,at)=(a1,…,at,1),ifat-1=at=1,θ-1(a1,…,at)={(a1,…,at-1,at+1),(a1,…,at,1)},pppppppppppppppppppppppppppppotherwise.
The resulting tree is
where the level𝒯m contains all the partitions of the integer m.Definition 8.
We call natural descent function of a rooted tree𝒯 the function ν𝒯 such that ν𝒯(a) is the parent node of a, for any node a∈𝒯.Definition 9.
Let us define the setU={n∈ℕ:ifp|nandq<pthenq|n}.Definition 10.
Let𝒰 be a descent tree, whose nodes are labeled by U. The structure of 𝒰 is determined by the following descent function:
(9)θU(a)=θ(∏i=1m‍pihi)=apmhm.The tree𝒰 is an infinite tree, whose nodes have infinite degree.Theorem 11.
Given any countable rooted tree𝒯, then there exists an injective function j:𝒯→𝒰, such that the following diagram is commutative:
(10)The functionj of the theorem can be defined recursively. The idea is to assign an element of x∈R to a node of 𝒯 that belongs to the kth floor, such that the prime pk is the greatest divisor of x. In particular, if ϵ is the root of 𝒯, then j(ϵ)=1. Moreover, let us suppose that j is defined over all elements of 𝒯 until the floor 𝒯k. A node a∈𝒯k+1 is the child of a node b∈𝒯k. If j(b)=p1e1p2e2…pkek and a is the sth child of b, then
(11)j(a)=p1e1p2e2…pkekpk+1s.
In this way, any countable rooted tree is contained in the universal tree 𝒰. Indeed, given a countable rooted tree 𝒯, it is determined by its natural descent function ν𝒯. Furthermore, ν𝒯 is the restriction of θU to 𝒯.Example 12.
Let us consider the following tree without label:
We can assign labels, embedding the tree into𝒰 in the following way:
that is,
The structure of the tree is determined by the descent function (9). For example, we can determine the paths of the node 30 as follows:
(12)θU(30)=θU(2·3·5)=2·3=6,θU(6)=θU(2·3)=2,θU(2)=1.Example 13.
The tree given in Example6 can be labeled as follows:
And consequently it can be derived by using the descent function (9). We can derive such a tree starting from U and θU. Given n∈U, let u(n) and h(n) be the exponent of the greatest prime that divides n and h(n) the index of the greatest prime that divides n in the sequence of prime numbers, respectively. Thus, the previous tree is defined by the following laws of growth:  (1)
1 generates 2;(2)
ifh(n)=k and u(n)=1, then n generates the children npk+1 and npk+12;(3)
ifh(n)=k and u(n)=2, then n generates the child npk+1.Now we focus on a class of rooted trees which satisfy the following.Definition 14.
Let us consider the rooted tree𝒯, whose nodes are labeled by the set X=⨃i=1vAi (disjoint union). We call types the sets Ai. The fact that a∈Ai, that is, a is a node of the type Ai, determines the number of its children and their type. We call 𝒯 a typed tree, and if a∈Ai, we indicate with sij the number of its children that are in Aj (i.e., the number of its children that have type Aj).In a typed tree, any node belongs to a type; that is, the number of children and their type is known. A similar class of tree is studied in [8, 9], where the nodes of the tree are labeled considering the number of children and their label.Remark 15.
In the following, we directly use typed trees to derive the order of the levels as recurrent sequences. A sequence(an)n=0∞ recurs with characteristic polynomial
(13)f(t)=tm-∑i=1m‍hitm-i,
if (an)n=0∞ satisfies the linear homogeneous recurrent relation
(14)an=∑i=1m‍hian-i,∀n≥m,
given the initial conditions a0,…,am-1. We also recall that the ordinary generating function related to a linear recurrent sequence is F(t)=u(t)/fR(t), where fR(t)=1-∑i=1m‍hiti is the reflected polynomial of f(t) and the polynomial u(t)=∑i=1m-1‍uiti is determined from initial conditions (see, e.g., [10] for a survey on recurrent sequences).Using previous notation, we can define thematrix of types as G=(sij). Such a matrix easily allows to determine the counting sequence of the levels as a linear recurrent sequence.Proposition 16.
The sequence(|𝒯m|)m=0∞ is a linear recurrent sequence whose characteristic polynomial is the characteristic polynomial of G.Proof.
Let us defineui(m)=|{x∈𝒯m:x∈Ai}|; then |𝒯m|=∑i=1v‍ui(m). Moreover, defining the distribution of the elements of 𝒯m as
(15)π(m)=(u1(m),…,uv(m)),
it is immediate that
(16)π(m)G=π(m+1).
It follows that any sequence (ui(m))m=0∞ recurs with the characteristic polynomial of G. Since |𝒯m| is the sum of the ui(m)’s, then it is wellknown that |𝒯m| is a linear recurrent sequence with the same characteristic polynomial of the ui(m)’s.Example 17.
Let us consider the tree constructed in Example6. We consider the partition ℕ=A1∪A2 where A1={n∈ℕ:nodd} and A2={n∈ℕ:neven}. Then G=(0111): odd numbers have only one child which is an even number; even numbers have two children (one odd and one even). As a consequence, the sequence of the levels orders of such tree is the Fibonacci sequence. Indeed, the characteristic polynomial of G is x2-x-1, and it is straightforward to check that |𝒯0|=1, |𝒯1|=1.Example 18.
Let us consider the tree constructed in Example7. This is an example of tree constructed via descent function which is not a typed tree. By Proposition 16 it follows that in a typed tree the orders of the levels are a linear recurrent sequence. In Example 7, |𝒯m| is the number of partitions of the integer m, and it is well known that such a sequence is not recurrent. Indeed, it is wellknown that the generating function of the sequence counting the number of partition of the integers is
(17)∏k>0‍11-xk.
That is not a rational function (see, e.g., sequence A000041 in [11]).
However, it is interesting to see that only changing the setX, the descent tree alters its structure and properties. Let us use the same set Y and functions w, θ of the Example 7, but we change X, taking the set of the vectors (a1,…,at) such that t≥1 and ai∈ℕ for every i. In this case, the inverse descent function is
(18)θ-1(a1,…,at)={(a1,…,at,1),(a1,…,at-1,at+1)},
and the descent tree is
SettingX=A1∪A2, where A1={a∈X:lastcomponent=1} and A2={a∈X:lastcomponent>1}, this is a generating tree. We easily see that G=(1111), whose characteristic polynomial is x2-2x. Thus, we have |𝒯m|=2m, for any m≥0.An important consequence of the use of descent functions for constructing trees is the possibility of composing trees to each other in order to obtain new ones. The composition of two descent trees is simple, and it is highlighted in the following.Definition 19.
Let𝒯, S be descent trees created by the generative tree systems (X,Y,w,f) and (X,Y,w,g), respectively. Let us consider any partition X=A∪B formed by two subsets. We define ℛ=𝒯∘A,B𝒮 as the composed descent tree whose associated generative system is (X,Y,w,jA,B), where
(19)jA,B:X*⟶X,jA,B(x)=f(x),∀x∈A,jA,B(x)=g(x),∀x∈B.It is easy to see that sincef and g are descent functions, the function jA,B is still a descent function, and therefore ℛ is still a descent tree. By Definition 19, it is clear that tree composition depends on the partition of X and on the order of the subsets A and B considered in (19). This means that any partition generates two different trees; that is,
(20)𝒯∘A,B𝒮≠𝒯∘B,A𝒮.In the next sections, we apply these tools to rational trees and Pythagorean trees.


## 3. Applications and Examples

### 3.1. Rational Trees

A rational tree is a tree such thatX=ℚ+, where every positive rational number appears in the tree exactly once and each node generates children following some explicit rule. Actually, only three rational trees are known: the Kepler tree [3], the Calkin-Wilf tree [2], and the Stern-Brocot tree [1, 4].The oldest, but the less famous, is the Kepler tree, introduced by Kepler in Harmonices Mundi in 1619. The Kepler tree is a binary tree, that is; each node has two children by means of the following rule:We can derive the Kepler tree via descent functions, by setting(21)X=ℚ+,Y=ℕ,w(ab)=a+b,ϵ=11,θK(ab)={a-bb,a>b,b-aa,a<b.Remark 20.
The fractionsa/b in rational trees are considered with a, b coprime.It is easy to see thatθK generates the Kepler tree:A similar tree, recently studied, is the Calkin-Wilf tree where the construction rule is given byWe can derive the corresponding generative system tree by means of(22)X=ℚ+,Y=ℕ,w(ab)=a+b,ϵ=11,θC(ab)={a-bb,a>b,ab-a,a<b,
from which we have the Calkin-Wilf tree:Now, we can apply the composition of descent functions stated in Definition19 to the generative systems tree (X,Y,w,θK) and (X,Y,w,θC) obtaining a new generative system tree (X,Y,w,θ), where, for example, we can construct θ as follows:
(23)θ(ab)={θK(ab),beven,θC(ab),bodd,={a-bb,a>b,b-aa,a<bandbeven,ab-a,a<bandbodd,
from which we can derive its inverse in order to construct the tree starting from the root 1/1 as follows:
(24)θ-1(ab)={aa+b,a+bb},ifa+bodd,θ-1(ab)={a+bb,ba+b},ifa+beven.
The generative system tree (X,Y,w,θ) generates the following tree:Such a tree is different from the Kepler, Calkin-Wilf, and Stern-Brocot trees. Moreover, every positive rational number appears exactly once in the tree. Indeed, given any rational numbera/b, there exists a positive integer n such that θn(a/b)=ϵ=1/1, since θ is a descent function for the system (X,Y,w,θ) by construction.Theorem 21.
The generative system tree(X,Y,w,θ), where
(25)X=ℚ+,Y=ℕ,w(ab)=a+b,∀ab∈X,θ(ab)={a-bb,a>b,b-aa,a<bandbeven,ab-a,a<bandbodd,
generates a rational tree.Remark 22.
Using different partitions ofℚ+ into two subsets, we can apply Definition 19 in order to compose Kepler and Calkin-Wilf trees to obtain a new rational tree. This is a very important result because in this way, we are able to construct infinite rational trees.Finally, we examine the Stern-Brocot tree from the point of view of the descent functions. The Stern-Brocot tree is a rational tree made up of mediants(a+b)/(c+d) of two fractions a/c and b/d, as described in Figure 2. It is not immediate to obtain the corresponding generative system tree (despite the Kepler and Calkin-Wilf cases). However, if we consider the 2×2 invertible matrices with determinant 1, we can find a descent function from which we can derive the Stern-Brocot tree. Precisely, we take the following:
(26)X=SL(2,ℕ),Y=ℕ,w([abcd])=a+b+c+d,ϵ=[1001],(27)θS([abcd])={[a-bbc-dd],[ac]>[bd][ab-acd-c],[ac]<[bd],
where [ac]>[bd] means
(28)a≥b,c≥d.Figure 2Remark 23.
Observe that, since the matrices considered ealier are invertible, equalities in (28) cannot hold simultaneously. Moreover, given a [abcd]∈SL(2,ℕ), [ac]>[bd] or [ac]<[bd] holds, except for ϵ.It is easy to observe that(29)θS-1([abcd])={[a+bbc+dd],[aa+bcc+d]},
using the following transformation,
(30)[abcd]⟶a+bc+d.
We can construct the Stern-Brocot tree by using the generative system tree (X,Y,w,θS).Remark 24.
The use of the descent functionθS provides a new explicit representation of the Stern-Brocot tree.In [12], a method involving continued fractions has been proposed in order to locate the position of any rational number over the Stern-Brocot tree. Here, we highlight an iterative method (involving the generative system tree (X,Y,w,θS)) to find the path of any rational number over the Stern-Brocot tree.Given any rational numbere/f in the Stern-Brocot tree (with e≠1), then it is the mediant of the fractions a/c, b/d, where
(31)a=f-1mode,b=e-a,c=af-1e,d=f-c.
Indeed, if e/f is the mediant of a/c and b/d we must have
(32)a+b=e,c+d=f,ad-bc=1,
and we obtain
(33)af-1=ac+ad-ad+bc=ac+bc=ce,
from which
(34)b=e-a,c=af-1e,d=f-c.
We only need to find a. Since e and f are coprime, f∈ℤe* and we obtain
(35)a=f-1mode.
If the rational number is 1/f the path on the Stern-Brocot tree is trivial to find.Thus, given any rational numbere/f, we are able to construct the corresponding matrix [abcd]∈SL(2,ℕ) such that a+b=e and c+d=f. Using the descent function θS, we have
(36)θS([abcd])=[a′b′c′d′],
according to (27), where (a′+b′)/(c′+d′) is the parent node of e/f in the Stern-Brocot tree. The iteration of the descent function θS provides the path of the rational number e/f.Example 25.
Let us consider the rational number11/8; then by (31) we have that in the Stern-Brocot tree 11/8 is the mediant of
(37)75,43,(38)θS([7453])=[3423].
Consequently the parent node of 11/8 is 7/5. Now, we know from (38) that 7/5 is the mediant of 3/2 and 4/3, and
(39)θS([3423])=[3121],
and the parent node of 7/5 is 4/3. Again, we have
(40)θS([3121])=[2111].
The parent node of 4/3 is 3/2. Similarly, we obtain that the parent node of 3/2 is 2/1, and finally we arrive to the root 1/1. Thus the path from the rational number 11/8 to the root in the Stern-Brocot tree is
(41)(118,75,43,32,21,11).


### 3.2. Pythagorean Trees

Pythagorean trees are trees of Pythagorean triples; that is, each node is a triple[a,b,c] of positive integers that satisfy the equation a2+b2=c2. In the following, we describe the two known Pythagorean trees in terms of descent functions introduced in Section 2. Moreover, we will find two new Pythagorean trees by simply applying the tree composition presented in Definition 19.We consider the setsY=2ℕ and X of all the couples (a,b) where a>b≥1 are odd coprime positive integers. The function
(42)w:X⟶Y,w((a,b))=a+b
satisfies the Definition 1 of weight function. As a matter of fact, Y is a partially ordered set with respect to the relation of strict total order < between integers, and we have ϵ=(3,1) such that w(ϵ)<w((a,b))forall(a,b)≠ϵ∈X, and also the third condition of Definition 1 is clearly satisfied. The two systems (X,Y,w,θ1) and (X,Y,w,θ2) where
(43)θ1((a,b))={(a-2b,b)ifa>3b,(b,a-2b)if2b<a<3b(b,2b-a)ifb<a<2b,,θ2((a,b))={(a+b2,b)ifa+b2isodd,(max(a-b2,b),min(a-b2,b))ifa-b2isodd,
are generative tree systems. Indeed, from (43), we immediately have for all x∈X* that w(θ1(x))<w(x) and w(θ2(x))<w(x), so the functions θ1 and θ2 are descent functions. Moreover, a simple calculation shows that
(44)θ1-1((a,b))={(a+2b,b),(2a+b,a),(2a-b,a)},(45)θ2-1((a,b))={(2a-b,b),(2a+b,b),(a+2b,a)}.
So we have a complete description of the two trees 𝒫𝒯1 and 𝒫𝒯2 corresponding to the generative tree systems (X,Y,w,θ1) and (X,Y,w,θ2), respectively. We show 𝒫𝒯1 to the third level as follows:and𝒫𝒯2 to the third level as follows:These trees are strictly related to the Pythagorean triples. As a matter of fact, we can observe their correspondence with the two trees presented in [7] where the second columns of the matrices in the nodes are exactly the nodes of our trees. Here every node (a,b) represents the primitive Pythagorean triple (ab,(a2-b2)/2,(a2+b2)/2). The tree 𝒫𝒯1 is the Barning-Hall tree [5, 6], while 𝒫𝒯2 is the new Pythagorean tree presented by Price [7]. Combining 𝒫𝒯1 and 𝒫𝒯2 by means of the composition rule stated in Definition 19, we can generate two new Pythagorean trees. As a first step, we have to find two disjoint subsets in X; for example, we can consider the most natural partition of the set of even numbers; namely,
(46)A1={(a,b)∈X:a=bmod4}={(a,b)∈X:a+b=2mod4},A2={(a,b)∈X:a≠bmod4}={(a,b)∈X:a+b=0mod4}.
Thanks to this partition of X, we obtain the two compositions
(47)Θ1((a,b))={θ1((a,b))if(a,b)∈A1,θ2((a,b))if(a,b)∈A2,Θ2((a,b))={θ1((a,b))if(a,b)∈A2,θ2((a,b))if(a,b)∈A1,
which clearly are descent functions. We easily determine their inverses using the definitions of θ1-1 and θ2-1 as follows. When (a,b)∈A1, we have for the elements belonging to the set (44)
(48)w((a+2b,b))=a+3b=0mod4⟹(a+2b,b)∈A2,w((2a+b,a))=3a+b=0mod4⟹(2a+b,a)∈A2,w((2a-b,a))=3a-b=2mod4⟹(2a-b,a)∈A1
for the elements of the set (45),
(49)w((2a-b,b))=2a=2mod4⟹(2a-b,b)∈A1,w((2a+b,b))=2a+2b=0,mod4⟹(2a+b,b)∈A2,w((a+2b,a))=2a+2b=0,mod4⟹(a+2b,a)∈A2.
On the other hand, when (a,b)∈A2 we have for the elements belonging to the set (44)
(50)w((a+2b,b))=a+3b=2mod4⟹(a+2b,b)∈A1,w((2a+b,a))=3a+b=2mod4⟹(2a+b,a)∈A1,w((2a-b,a))=3a-b=0mod4⟹(2a-b,a)∈A2;
for the elements of the set (45), the situation is the same as in (49). Therefore, if we use Θ1, we reach (a,b)∈A1 from the node (2a-b,a)∈A1 using θ1 or from the nodes (2a+b,b),(a+2b,a)∈A2 using θ2. Moreover, we reach (a,b)∈A2 from the nodes (a+2b,b),(2a+b,b)∈A1 using θ1, and from the nodes (2a+b,b),(a+2b,a)∈A2 using θ2. This allows us to invert Θ1 in this way as follows:
(51)Θ1-1((a,b))={{(2a-b,a),(2a+b,b),(a+2b,a)}ppppppppppppppppppppppppif(a,b)∈A1,{(a+2b,b),(2a+b,a),(2a+b,b),(a+2b,a)}ppppppppppppppppppppppppif(a,b)∈A2.
With similar considerations on Θ2, we obtain
(52)Θ2-1((a,b))={{(2a-b,b),(2a+b,a),(a+2b,b)}if(a,b)∈A1,{(2a-b,a),(2a-b,b)}if(a,b)∈A2.
The system (X,Y,w,Θ1) generates the tree 𝒫𝒯3=𝒫𝒯1∘A1,A2𝒫𝒯2 which we show to the third levelThe system(X,Y,w,Θ2) gives rise to the tree 𝒫𝒯4=𝒫𝒯1∘A2,A1𝒫𝒯2 whose first three levels appear as in Figure 3.Figure 3The partition ofX in the two subsets A1 and A2 allows us to complete our analysis of the four Pythagorean trees that we have considered.Remark 26.
We point out some interesting results which are straightforward applications of our approach. For each of the four Pythagorean trees described ealier, we are able to determine the related generating matrix and consequently to study the sequence of the order of themth level for m≥0. In fact, from relations (48),(49), and (50) it easily follows that  (i)
the generating matrix for𝒫𝒯1 is G1=(1221) whose characteristic polynomial is x2-4x+3, with roots x=3 and x=1;(ii)
the generating matrix for𝒫𝒯2 is G2=(1212) whose characteristic polynomial is x2-3x with roots x=0 and x=3;(iii)
the generating matrix for𝒫𝒯3 is G3=(1222) whose characteristic polynomial is x2-3x-2 with roots x=(3+17)/2 and x=(3-17)/2;(iv)
the generating matrix for𝒫𝒯4 is G4=(1211) whose characteristic polynomial is x2-2x-1 with roots x=1+2 and x=1-2. Clearly, the mth level order of 𝒫𝒯1 and 𝒫𝒯2 is the same as follows:
(53)|𝒫𝒯m1|=|𝒫𝒯m2|=3m.
The mth level order of 𝒫𝒯3 is
(54)|𝒫𝒯m3|=5+17217(3+172)m-5-17217(3-172)m.
We observe that the sequence of level orders has ordinary generating function (see [10]) given by
(55)F𝒫𝒯3(t)=1+t1-3t-2t2=1+4t+14t2+50t3+178t4+634t5+2258t6+8042t7+28642t8+O(t9),
and (|𝒫𝒯m3|)m=0+∞=(1,4,14,50,178,634,2258,8042,28642,…) is a sequence not present in the OEIS.
Finally, themth level order of 𝒫𝒯4 is
(56)|𝒫𝒯m4|=122[(1+2)m+1-(1-2)m+1].
The sequence (|𝒫𝒯m4|)m=0+∞ is surprisingly the sequence A000129 of Pell numbers described in OEIS.


## 3.1. Rational Trees

A rational tree is a tree such thatX=ℚ+, where every positive rational number appears in the tree exactly once and each node generates children following some explicit rule. Actually, only three rational trees are known: the Kepler tree [3], the Calkin-Wilf tree [2], and the Stern-Brocot tree [1, 4].The oldest, but the less famous, is the Kepler tree, introduced by Kepler in Harmonices Mundi in 1619. The Kepler tree is a binary tree, that is; each node has two children by means of the following rule:We can derive the Kepler tree via descent functions, by setting(21)X=ℚ+,Y=ℕ,w(ab)=a+b,ϵ=11,θK(ab)={a-bb,a>b,b-aa,a<b.Remark 20.
The fractionsa/b in rational trees are considered with a, b coprime.It is easy to see thatθK generates the Kepler tree:A similar tree, recently studied, is the Calkin-Wilf tree where the construction rule is given byWe can derive the corresponding generative system tree by means of(22)X=ℚ+,Y=ℕ,w(ab)=a+b,ϵ=11,θC(ab)={a-bb,a>b,ab-a,a<b,
from which we have the Calkin-Wilf tree:Now, we can apply the composition of descent functions stated in Definition19 to the generative systems tree (X,Y,w,θK) and (X,Y,w,θC) obtaining a new generative system tree (X,Y,w,θ), where, for example, we can construct θ as follows:
(23)θ(ab)={θK(ab),beven,θC(ab),bodd,={a-bb,a>b,b-aa,a<bandbeven,ab-a,a<bandbodd,
from which we can derive its inverse in order to construct the tree starting from the root 1/1 as follows:
(24)θ-1(ab)={aa+b,a+bb},ifa+bodd,θ-1(ab)={a+bb,ba+b},ifa+beven.
The generative system tree (X,Y,w,θ) generates the following tree:Such a tree is different from the Kepler, Calkin-Wilf, and Stern-Brocot trees. Moreover, every positive rational number appears exactly once in the tree. Indeed, given any rational numbera/b, there exists a positive integer n such that θn(a/b)=ϵ=1/1, since θ is a descent function for the system (X,Y,w,θ) by construction.Theorem 21.
The generative system tree(X,Y,w,θ), where
(25)X=ℚ+,Y=ℕ,w(ab)=a+b,∀ab∈X,θ(ab)={a-bb,a>b,b-aa,a<bandbeven,ab-a,a<bandbodd,
generates a rational tree.Remark 22.
Using different partitions ofℚ+ into two subsets, we can apply Definition 19 in order to compose Kepler and Calkin-Wilf trees to obtain a new rational tree. This is a very important result because in this way, we are able to construct infinite rational trees.Finally, we examine the Stern-Brocot tree from the point of view of the descent functions. The Stern-Brocot tree is a rational tree made up of mediants(a+b)/(c+d) of two fractions a/c and b/d, as described in Figure 2. It is not immediate to obtain the corresponding generative system tree (despite the Kepler and Calkin-Wilf cases). However, if we consider the 2×2 invertible matrices with determinant 1, we can find a descent function from which we can derive the Stern-Brocot tree. Precisely, we take the following:
(26)X=SL(2,ℕ),Y=ℕ,w([abcd])=a+b+c+d,ϵ=[1001],(27)θS([abcd])={[a-bbc-dd],[ac]>[bd][ab-acd-c],[ac]<[bd],
where [ac]>[bd] means
(28)a≥b,c≥d.Figure 2Remark 23.
Observe that, since the matrices considered ealier are invertible, equalities in (28) cannot hold simultaneously. Moreover, given a [abcd]∈SL(2,ℕ), [ac]>[bd] or [ac]<[bd] holds, except for ϵ.It is easy to observe that(29)θS-1([abcd])={[a+bbc+dd],[aa+bcc+d]},
using the following transformation,
(30)[abcd]⟶a+bc+d.
We can construct the Stern-Brocot tree by using the generative system tree (X,Y,w,θS).Remark 24.
The use of the descent functionθS provides a new explicit representation of the Stern-Brocot tree.In [12], a method involving continued fractions has been proposed in order to locate the position of any rational number over the Stern-Brocot tree. Here, we highlight an iterative method (involving the generative system tree (X,Y,w,θS)) to find the path of any rational number over the Stern-Brocot tree.Given any rational numbere/f in the Stern-Brocot tree (with e≠1), then it is the mediant of the fractions a/c, b/d, where
(31)a=f-1mode,b=e-a,c=af-1e,d=f-c.
Indeed, if e/f is the mediant of a/c and b/d we must have
(32)a+b=e,c+d=f,ad-bc=1,
and we obtain
(33)af-1=ac+ad-ad+bc=ac+bc=ce,
from which
(34)b=e-a,c=af-1e,d=f-c.
We only need to find a. Since e and f are coprime, f∈ℤe* and we obtain
(35)a=f-1mode.
If the rational number is 1/f the path on the Stern-Brocot tree is trivial to find.Thus, given any rational numbere/f, we are able to construct the corresponding matrix [abcd]∈SL(2,ℕ) such that a+b=e and c+d=f. Using the descent function θS, we have
(36)θS([abcd])=[a′b′c′d′],
according to (27), where (a′+b′)/(c′+d′) is the parent node of e/f in the Stern-Brocot tree. The iteration of the descent function θS provides the path of the rational number e/f.Example 25.
Let us consider the rational number11/8; then by (31) we have that in the Stern-Brocot tree 11/8 is the mediant of
(37)75,43,(38)θS([7453])=[3423].
Consequently the parent node of 11/8 is 7/5. Now, we know from (38) that 7/5 is the mediant of 3/2 and 4/3, and
(39)θS([3423])=[3121],
and the parent node of 7/5 is 4/3. Again, we have
(40)θS([3121])=[2111].
The parent node of 4/3 is 3/2. Similarly, we obtain that the parent node of 3/2 is 2/1, and finally we arrive to the root 1/1. Thus the path from the rational number 11/8 to the root in the Stern-Brocot tree is
(41)(118,75,43,32,21,11).


## 3.2. Pythagorean Trees

Pythagorean trees are trees of Pythagorean triples; that is, each node is a triple[a,b,c] of positive integers that satisfy the equation a2+b2=c2. In the following, we describe the two known Pythagorean trees in terms of descent functions introduced in Section 2. Moreover, we will find two new Pythagorean trees by simply applying the tree composition presented in Definition 19.We consider the setsY=2ℕ and X of all the couples (a,b) where a>b≥1 are odd coprime positive integers. The function
(42)w:X⟶Y,w((a,b))=a+b
satisfies the Definition 1 of weight function. As a matter of fact, Y is a partially ordered set with respect to the relation of strict total order < between integers, and we have ϵ=(3,1) such that w(ϵ)<w((a,b))forall(a,b)≠ϵ∈X, and also the third condition of Definition 1 is clearly satisfied. The two systems (X,Y,w,θ1) and (X,Y,w,θ2) where
(43)θ1((a,b))={(a-2b,b)ifa>3b,(b,a-2b)if2b<a<3b(b,2b-a)ifb<a<2b,,θ2((a,b))={(a+b2,b)ifa+b2isodd,(max(a-b2,b),min(a-b2,b))ifa-b2isodd,
are generative tree systems. Indeed, from (43), we immediately have for all x∈X* that w(θ1(x))<w(x) and w(θ2(x))<w(x), so the functions θ1 and θ2 are descent functions. Moreover, a simple calculation shows that
(44)θ1-1((a,b))={(a+2b,b),(2a+b,a),(2a-b,a)},(45)θ2-1((a,b))={(2a-b,b),(2a+b,b),(a+2b,a)}.
So we have a complete description of the two trees 𝒫𝒯1 and 𝒫𝒯2 corresponding to the generative tree systems (X,Y,w,θ1) and (X,Y,w,θ2), respectively. We show 𝒫𝒯1 to the third level as follows:and𝒫𝒯2 to the third level as follows:These trees are strictly related to the Pythagorean triples. As a matter of fact, we can observe their correspondence with the two trees presented in [7] where the second columns of the matrices in the nodes are exactly the nodes of our trees. Here every node (a,b) represents the primitive Pythagorean triple (ab,(a2-b2)/2,(a2+b2)/2). The tree 𝒫𝒯1 is the Barning-Hall tree [5, 6], while 𝒫𝒯2 is the new Pythagorean tree presented by Price [7]. Combining 𝒫𝒯1 and 𝒫𝒯2 by means of the composition rule stated in Definition 19, we can generate two new Pythagorean trees. As a first step, we have to find two disjoint subsets in X; for example, we can consider the most natural partition of the set of even numbers; namely,
(46)A1={(a,b)∈X:a=bmod4}={(a,b)∈X:a+b=2mod4},A2={(a,b)∈X:a≠bmod4}={(a,b)∈X:a+b=0mod4}.
Thanks to this partition of X, we obtain the two compositions
(47)Θ1((a,b))={θ1((a,b))if(a,b)∈A1,θ2((a,b))if(a,b)∈A2,Θ2((a,b))={θ1((a,b))if(a,b)∈A2,θ2((a,b))if(a,b)∈A1,
which clearly are descent functions. We easily determine their inverses using the definitions of θ1-1 and θ2-1 as follows. When (a,b)∈A1, we have for the elements belonging to the set (44)
(48)w((a+2b,b))=a+3b=0mod4⟹(a+2b,b)∈A2,w((2a+b,a))=3a+b=0mod4⟹(2a+b,a)∈A2,w((2a-b,a))=3a-b=2mod4⟹(2a-b,a)∈A1
for the elements of the set (45),
(49)w((2a-b,b))=2a=2mod4⟹(2a-b,b)∈A1,w((2a+b,b))=2a+2b=0,mod4⟹(2a+b,b)∈A2,w((a+2b,a))=2a+2b=0,mod4⟹(a+2b,a)∈A2.
On the other hand, when (a,b)∈A2 we have for the elements belonging to the set (44)
(50)w((a+2b,b))=a+3b=2mod4⟹(a+2b,b)∈A1,w((2a+b,a))=3a+b=2mod4⟹(2a+b,a)∈A1,w((2a-b,a))=3a-b=0mod4⟹(2a-b,a)∈A2;
for the elements of the set (45), the situation is the same as in (49). Therefore, if we use Θ1, we reach (a,b)∈A1 from the node (2a-b,a)∈A1 using θ1 or from the nodes (2a+b,b),(a+2b,a)∈A2 using θ2. Moreover, we reach (a,b)∈A2 from the nodes (a+2b,b),(2a+b,b)∈A1 using θ1, and from the nodes (2a+b,b),(a+2b,a)∈A2 using θ2. This allows us to invert Θ1 in this way as follows:
(51)Θ1-1((a,b))={{(2a-b,a),(2a+b,b),(a+2b,a)}ppppppppppppppppppppppppif(a,b)∈A1,{(a+2b,b),(2a+b,a),(2a+b,b),(a+2b,a)}ppppppppppppppppppppppppif(a,b)∈A2.
With similar considerations on Θ2, we obtain
(52)Θ2-1((a,b))={{(2a-b,b),(2a+b,a),(a+2b,b)}if(a,b)∈A1,{(2a-b,a),(2a-b,b)}if(a,b)∈A2.
The system (X,Y,w,Θ1) generates the tree 𝒫𝒯3=𝒫𝒯1∘A1,A2𝒫𝒯2 which we show to the third levelThe system(X,Y,w,Θ2) gives rise to the tree 𝒫𝒯4=𝒫𝒯1∘A2,A1𝒫𝒯2 whose first three levels appear as in Figure 3.Figure 3The partition ofX in the two subsets A1 and A2 allows us to complete our analysis of the four Pythagorean trees that we have considered.Remark 26.
We point out some interesting results which are straightforward applications of our approach. For each of the four Pythagorean trees described ealier, we are able to determine the related generating matrix and consequently to study the sequence of the order of themth level for m≥0. In fact, from relations (48),(49), and (50) it easily follows that  (i)
the generating matrix for𝒫𝒯1 is G1=(1221) whose characteristic polynomial is x2-4x+3, with roots x=3 and x=1;(ii)
the generating matrix for𝒫𝒯2 is G2=(1212) whose characteristic polynomial is x2-3x with roots x=0 and x=3;(iii)
the generating matrix for𝒫𝒯3 is G3=(1222) whose characteristic polynomial is x2-3x-2 with roots x=(3+17)/2 and x=(3-17)/2;(iv)
the generating matrix for𝒫𝒯4 is G4=(1211) whose characteristic polynomial is x2-2x-1 with roots x=1+2 and x=1-2. Clearly, the mth level order of 𝒫𝒯1 and 𝒫𝒯2 is the same as follows:
(53)|𝒫𝒯m1|=|𝒫𝒯m2|=3m.
The mth level order of 𝒫𝒯3 is
(54)|𝒫𝒯m3|=5+17217(3+172)m-5-17217(3-172)m.
We observe that the sequence of level orders has ordinary generating function (see [10]) given by
(55)F𝒫𝒯3(t)=1+t1-3t-2t2=1+4t+14t2+50t3+178t4+634t5+2258t6+8042t7+28642t8+O(t9),
and (|𝒫𝒯m3|)m=0+∞=(1,4,14,50,178,634,2258,8042,28642,…) is a sequence not present in the OEIS.
Finally, themth level order of 𝒫𝒯4 is
(56)|𝒫𝒯m4|=122[(1+2)m+1-(1-2)m+1].
The sequence (|𝒫𝒯m4|)m=0+∞ is surprisingly the sequence A000129 of Pell numbers described in OEIS.



---

*Source: 543913-2013-08-27.xml*