The rational numbers are countable: they can be put into one-to-one correspondence with the natural numbers. But it is not obvious how to construct a list that is sure to contain every rational number precisely once. In a previous post we described the Farey Sequences. Here we examine another, related, approach.

**The Stern-Brocot Tree**

We consider a tree structure that contains each positive rational number precisely once. It was devised independently by Moritz Stern, a German number theorist and Achille Brocot, a French clockmaker. Brocot was interested in designing gear systems with specific gear ratios, constrained by engineering practicalities.

We start with two boundary values, to represent and to represent . They are not members of the tree, but are used to generate new entries by forming mediants. Recall that the mediant of two rational numbers and is

and its value always falls between the two numbers.

The root of the tree is , which is the mediant of the boundary values. Thus, at Level 1 we have three numbers . This is the first Stern-Brocot sequence. To construct a new level, we form the mediant of each adjacent pair of ratios in the level above. Thus, if there are entries at level , there are new entries at Level . If we now carry down the numbers at Level to Level , we get the st Stern-Brocot sequence, which has entries. This is then used to generate the new entries of the sequence at Level .

If we include only new entries at each level, we see that all rationals can be included in a tree structure (see Figure below), and each rational occurs precisely once. Every branch of the tree bifurcates at every level. Each number in the tree has two “children” but only one “parent”. For a rational , the left child is smaller than while the right child is greater. Explicit values for the children can be expressed in terms of continued fractions.

The Stern-Brocot sequence of order , which comprises all entries in the first levels of the tree, together with the two boundary values, arranged in ascending order, has ratios. For example, the 4 sequence isFor comparison, the 4 Farey sequence is

The process of generating the Stern-Brocot tree has some similarity to that used to generate the Farey sequences. But, at each stage, all the mediants are included, not only those having a specific value of the denominator. Moreover, the Stern-Brocot tree includes all positive rationals, not just those in the interval .

Stern-Brocot sequences of orders 1 to 4, arranged to show new entries at each stage.

**The Calkin-Wilf Tree
**

In a following article, we will introduce another structure, the Calkin-Wilf Tree. It is quite similar to the Stern-Brocot tree, but the differences are interesting.

** Sources **

Wikipedia article *Stern-Brocot Tree*.

You must be logged in to post a comment.