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." http://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." http://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 Web Resource. https://mathworld.wolfram.com/Calkin-WilfTree.html