This site is supported by donations to The OEIS Foundation.

# The Stern-Brocot or Farey Tree

(Redirected from Stern-Brocot tree)

There are several versions of this tree. This one, which appears in (Graham, Knuth and Patashnik 1990, p. 117), was drawn by Alexander Bogomolny[1]. For another version see J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.

The nth order Farey series is the set of reduced fractions between 0 and 1 whose denominators are n or less, arranged in increasing order, and corresponds to a subtree of the Stern-Brocot tree.

There are also many associated sequences:

• The numerators and denominators of the fractions in the full tree give A007305/A047679.
• The numerators and denominators of the fractions in the left-hand subtree give A007305/A007306.
• The numerators and denominators of the triangle whose nth row consists of the Farey series of order n give A006842/A006843.

## Extensions to the Stern-Brocot tree

One way to extend the Stern-Brocot tree to cover whole ${\displaystyle \scriptstyle \mathbb {Q} \,}$, not just the positive rationals, is to reflect it over the "Y-axis" where zero, (i.e. fraction ${\displaystyle \scriptstyle {\frac {0}{1}}\,}$) is located, and make the fractions on the left side all negative. (See A057114 for example.) (XXX - We need here an illustration like above.)

## References

• Graham, R. L.; Knuth, D. E. & Patashnik, O. (1990). Concrete Mathematics. Reading, MA: Addison-Wesley.

## Authorship

The original version of this page was written by Neil Sloane. (The initial version was copied from http://oeis.org/stern_brocot.html but is intended to be filled with more information!)