A Calkin-Wilf tree is a special type of binary tree obtained by starting with the fraction 
and iteratively adding 
and 
below each fraction 
. The Stern-Brocot
tree is closely related, putting 
and 
below each fraction 
. Both trees
generate every rational number. Writing out the
terms in sequence gives 1/1, 1/2, 2/1, 1/3, 3/2, 2/3,
3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, ...The sequence
has the property that each denominator is the next
numerator. This sequence,
1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... (OEIS A002487),
is known as Stern's diatomic series, or
the fusc function (Dijkstra 1982).
Calkin-Wilf Tree
See also
Binary Tree, Stern-Brocot Tree, Stern's Diatomic SeriesExplore with Wolfram|Alpha
References
Bogomolny, A. "Fractions on a Binary Tree II." https://www.cut-the-knot.org/blue/Fusc.shtml.Calkin, N. and Wilf, H. S. "Recounting the Rationals." Amer. Math. Monthly 107, 360-363, 2000.Dijkstra, E. W. Selected Writings on Computing: A Personal Perspective. New York: Springer-Verlag, pp. 215-232, 1982.Gibbons, L.; Lester, D.; and Bird, R. "Functional Pearl: Enumerating the Rationals." J. Func. Prog. 16, 281-291, 2006.
Schneider, K. "The Tree of All Fractions."
2007. https://demonstrations.wolfram.com/TheTreeOfAllFractions/.Sloane,
N. J. A. Sequence A002487/M0141
in "The On-Line Encyclopedia of Integer Sequences."Referenced on Wolfram|Alpha
Calkin-Wilf TreeCite this as:
Weisstein, Eric W. "Calkin-Wilf Tree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Calkin-WilfTree.html