Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Calkin–Wilf tree
open-in-new
<p>In <a href="/facts/Number_theory/zhoa7zrc">number theory</a>, the Calkin–Wilf tree is a <a href="/facts/Tree_(graph_theory)/TCWk4Joy">tree</a> in which the <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertices</a> correspond <a href="/facts/Bijection/j4gTuTmW">one-to-one</a> to the <a href="/facts/Positive_number/z0xollg1">positive</a> <a href="/facts/Rational_number/VJQmyY05">rational numbers</a>. The tree is rooted at the number 1, and any rational number q expressed in simplest terms as the <a href="/facts/Fraction_(mathematics)/ghnQE9B3">fraction</a> <i>a</i>/<i>b</i> has as its two children the numbers 1/1+1/<i>q</i> = <i>a</i>/<i>a</i> + <i>b</i> and <i>q</i> + 1 = <i>a</i> + <i>b</i>/<i>b</i>. Every positive rational number appears exactly once in the tree. It is named after <a href="/facts/Neil_Calkin/HoYwxkWh">Neil Calkin</a> and <a href="/facts/Herbert_Wilf/SpfnF0dc">Herbert Wilf</a>, but appears in other works including <a href="/facts/Johannes_Kepler/wk6GTN3C">Kepler's</a> <i><a href="/facts/Harmonices_Mundi/BDKcKU7Y">Harmonices Mundi</a></i>. </p><p>The sequence of rational numbers in a <a href="/facts/Breadth-first_search/2kulDXCx">breadth-first traversal</a> of the Calkin–Wilf tree is known as the Calkin–Wilf sequence. Its sequence of numerators (or, offset by one, denominators) is Stern's diatomic series, and can be computed by the fusc function. </p>