Stern-Brocot tree


If we start with irreducible fractions representing zero and infinity,

01,10,

and then between adjacent fractions mn and mn we insert fraction m+mn+n, then we obtain

01,11,10.

Repeating the process, we get

01,12,11,21,10,

and then

01,13,12,23,11,32,21,31,10,

and so forth. It can be proven that every irreducible fraction appears at some iteration and no fraction ever appears twice [1]. The process can be represented graphically by means of so-called Stern-Brocot treeMathworldPlanetmath, named after its discoverers, Moritz Stern and Achille Brocot.

{xy}*!C\xybox\xymatrix@C=0.4em01\ar@.[d]&&&&&&&&11\ar@-[lllld]\ar@.[d]\ar@-[rrrrd]&&&&&&&&10\ar@.[d]01\ar@.[d]&&&&12\ar@-[lld]\ar@.[d]\ar@-[rrd]&&&&11\ar@.[d]&&&&21\ar@-[lld]\ar@.[d]\ar@-[rrd]&&&&10\ar@.[d]01\ar@.[d]&&13\ar@-[ld]\ar@.[d]\ar@-[rd]&&12\ar@.[d]&&23\ar@-[ld]\ar@.[d]\ar@-[rd]&&11\ar@.[d]&&32\ar@-[ld]\ar@.[d]\ar@-[rd]&&21\ar@.[d]&&31\ar@-[ld]\ar@.[d]\ar@-[rd]&&10\ar@.[d]01\ar@.+<0em,-5ex>&14\ar@-+<-0.5em,-5ex>\ar@.+<0em,-5ex>\ar@-+<0.5em,-5ex>&13\ar@.+<0em,-5ex>&25\ar@-+<-0.5em,-5ex>\ar@.+<0em,-5ex>\ar@-+<0.5em,-5ex>&12\ar@.+<0em,-5ex>&35\ar@-+<-0.5em,-5ex>\ar@.+<0em,-5ex>\ar@-+<0.5em,-5ex>&23\ar@.+<0em,-5ex>&34\ar@-+<-0.5em,-5ex>\ar@.+<0em,-5ex>\ar@-+<0.5em,-5ex>&11\ar@.+<0em,-5ex>&43\ar@-+<-0.5em,-5ex>\ar@.+<0em,-5ex>\ar@-+<0.5em,-5ex>&32\ar@.+<0em,-5ex>&53\ar@-+<-0.5em,-5ex>\ar@.+<0em,-5ex>\ar@-+<0.5em,-5ex>&21\ar@.+<0em,-5ex>&52\ar@-+<-0.5em,-5ex>\ar@.+<0em,-5ex>\ar@-+<0.5em,-5ex>&31\ar@.+<0em,-5ex>&41\ar@-+<-0.5em,-5ex>\ar@.+<0em,-5ex>\ar@-+<0.5em,-5ex>&10\ar@.+<0em,-5ex>

If we specify position of a fraction in the tree as a path consisting of L(eft) an R(ight) moves along the tree starting from the top (fraction 11), and also define matrices

L=[1101],R=[1011],

then product of the matrices corresponding to the path is matrix [nnmm] whose entries are numerators and denominators of parent fractions. For example, the path leading to fraction 35 is LRL. The corresponding matrix productMathworldPlanetmath is

LRL=[1101][1011][1101]=[2312],

and the parents of 35 are 12 and 23.

Continued fractionsDlmfMathworldPlanetmath and Stern-Brocot tree are closely related. A continued fraction a0;a1,a2, corresponds to fraction whose path from the top is Ra0La1Ra2 with the last element removed. For example,

53 =1+11+12=1;1,2=R1L1R2-1=RLR,
411 =0+12+11+13=0;2,1,3=R0L2R1L3-1=LLRLL.

The irrational numbers correspond to the infinite paths in the Stern-Brocot tree. For example, the golden mean ϕ=1;1,1,1, corresponds to the infinite path RLRLR. In particular, the denominator of the fraction corresponding to the string RLR of length n is the n’th Fibonacci numberDlmfMathworldPlanetmath.

References

  • 1 Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete Mathematics. Addison-Wesley, 1998. http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0836.00001Zbl 0836.00001.
Title Stern-Brocot tree
\metatable