The rational numbers are dense in the real numbers . The cardinality of rational numbers in the interval is . We cannot list them in ascending order, because there is no least rational number greater than .

However, there are several ways of enumerating the rational numbers. The best-known are

- The Calkin-Wilf Tree
- The Stern Brocot Tree
- The Farey sequences.

In Fig. 1 we show the first two of these enumerations. For the Calkin-Wilf Tree (left panel), we start with . Then, each number branches to two “children”. Below the rational number we have and . The mnemonic for this is: The *children* are “top over sum” and “sum over bottom”.

The Calkin-Wilf Tree has the structure of a pure binary tree. The Stern-Brocot tree (right panel) differs from this: each number has two “parents” and is formed as the mediant: the parents and produce .

** The Farey Sequences**

The Farey sequence of order is the sequence of (reduced) fractions between and which have denominators less than or equal to , arranged in order of increasing size. Each Farey sequence starts with the value or and ends with the value or . Thus, the eighth *Farey Sequence* is

A table of all the sequences up to order eight is shown here:

Farey sequences of orders 1 to 8, arranged to show new entries at each stage.

The numbers in this table are arranged to show, at the top of each column, the new rationals entering at each stage. John Farey speculated, in 1816, that each new entry is the mediant of its neighbours.

** The Fairy Lights**

We now eliminate from each row, any entry that has already appeared above it:

In an earlier post we showed how there are three parity classes for the rational numbers:

where and represent arbitrary odd and even integers. Replacing each entry by its parity, odd, even or none, now denoted by , and , we obtain the following tree:

It appears that the three parity types occur with about the same frequency. Indeed, counting the proportions for increading values of the denominators, we find that they all tend to the limit . This is shown in the Figure below:

The pattern of parities in the Farey Tree are seen by colouring the three types as follows: Even Blue; Odd Green; None Red. This is shown in the Figure at the head of this post.

The Farey sequences are closely related to the Stern-Brocot Tree and the Calkin-Wilf Tree, discussed in earlier posts to this blog. In Chapter 3 of * An Introduction to the Theory of Numbers*, Hardy and Wright give a short account of the curious history of Farey Sequences. John Farey stated the key properties without proving them. Cauchy provided proofs and ascribed the credit to Farey. But the theorems had been stated and proved much earlier by Haros (Hardy and Wright, p. 36).

** Sources**

Hardy, Godfrey Harold and Wright, E. M. (1960): *An Introduction to the Theory of Numbers* (Fourth Ed.), Oxford, at the Clarendon Press.

Wikipedia article *Farey Sequences*: \url{http://www.wikipedia.org/}