The rational numbers are countable: they can be put into one-to-one correspondence with the natural numbers. In previous articles we showed how the rationals can be presented as a list that includes each rational precisely once. One approach leads to the Farey Sequences. A second, related, approach gives us the Stern-Brocot Tree. Here, we introduce another tree structure, The Calkin-Wilf Tree.

**The Calkin-Wilf Tree**

The Calkin-Wilf Tree is quite similar to the Stern-Brocot tree, but the differences are interesting. The structure, devised by Neil Calkin and Herbert Wilf in 2000, contains each positive rational number precisely once. The tree starts with the root value .

**Each rational in the tree has two “children”. For the entry , the children are and . We note that the “left child” is always smaller than 1 while the “right child” is always greater than 1.**

At Level 1 we have one number, , and at Level 2 we have two, . At Level there are ratios. To construct Level , we form thetwo children of each entry in Level . Every branch of the tree bifurcates at every level.

**The CW Tree is complete**

The Calkin-Wilf tree is complete: it is easy to show that each positive rational number occurs precisely once. Considering a rational number less than 1, we see that it is the child of which has a smaller denominator. For a rational number greater than 1, the parent is which has a smaller numerator. If there are any missing rationals, there must be one such that is minimum. But we can link back to either or to . Both of these numbers have a sum of numerator and denominator that is less than . This contradiction forces us to conclude that no such exists and that the tree must include all positive rationals.

** The Kepler Tree **

There is nothing new under the Sun: in his book *Harmonices Mundi* (The Harmony of the World, 1619), Johannes Kepler presented a tree structure that is closely related to the Calkin-Wilf tree. Kepler’s tree is shown in the FIgure below (from Kepler, Book 3, page 27). It contains all rational numbers between and . Chapter 2 of Book 3 is entitled “On the Harmonic Divisions of the String”. Kepler analyses the properties of a string divided into two parts having small number ratios. On page 163 of *Harmonices Mundi* he writes: “The harmonic divisions of a single string are seven in number, not more.” He presents a numerical tree giving the origin of the seven ratios. The root of the tree is and, for any entry the two children are and .

Kepler writes “Let the diligent reader read what I wrote about these divisions 22 years ago in *The Secret of the Universe*, Chapter XII.” He then explains at length how he came to realize that the origin of the seven harmonies is to be found in the properties of constructable plane polygons. He stressed that he followed the evidence of his own ears in reaching his conclusions, not just blind reasoning, which could “drag the ears astray, ordering them to become deaf”.

The elements of the Calkin-Wilf tree and Kepler’s tree are shown below. Notice that, while the CW tree includes all positive rationals, the entries in Kepler’s tree are confined to the interval .

** Stern-Brocot and Calkin-Wilf Trees **

The construction of the Calkin-Wilf Tree is simpler than that of the Stern-Brocot tree: There is no need to introduce boundary values and , and only one value is used to generate two new values. Everything springs from the root . But CW lacks some nice properties of the SB tree: in the latter, the values at each level are arranged in increasing magnitude, and the structure can be used as a binary search tree. Both CW and SB are binary trees and both contain all positive rational numbers. Moreover, the same numbers appear at each level in each.

** Sources **

Calkin, Neil Calkin and Herbert S. Wilf, 1999: Recounting the rationals. *American Mathematical Monthly, 107, (4), 360–363. PDF*

Johannes Kepler: 1619: *Harmonices Mundi.* Translation (The Harmony of the World) by Eric J Aiton et al. Series: Memoirs of the American Philosophical Society, 209. American Philosophical Society, Philadelphia, 1997.

Wikipedia article *Calkin-Wilf Tree.*

You must be logged in to post a comment.