Arbre de Stern-Brocot

En la teoria dels nombres, l'arbre de Stern-Brocot és una estructura que permet d'enumerar tots els nombres racionals no negatius, així com un punt que representa l'infinit, representat formalment per 1/0. Fou descoberta de forma independent per Moritz Abraham Stern (1858) i Achille Brocot (1860).

Aquest arbre es pot crear mitjançant un procés iteratiu, que es pot descriure de forma senzilla com a llista. Començant amb la llista {0/1, 1/0}, que representa el zero i l'infinit, s'insereix entre cada dues fraccions la fracció mediant. Els primers passos d'aquest procés són:

• {0/1, 1/0}
• {0/1, 1/1, 1/0}
• {0/1, 1/2, 1/1, 2/1, 1/0}
• {0/1, 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1, 1/0}

Aquest procés es pot representar mitjançant un arbre en què cada nivell correspon als nombres que s'afegeixen en cada iteració.

Stern-Brocot tree

Tot nombre racional no negatiu apareix en aquest arbre exactament una vegada, en la seva forma irreductible, amb numerador i denominador primers entre si.

L'arbre és estretament lligat al concepte de fracció contínua simple en forma canònica. El valor de qualsevol fracció contínua simple en forma canònica [a₀;a₁,a₂,...,a_n] s'obté començant al node 1/1 i triant el camí dret a₀ vegades, després el camí esquerre a₁ vegades, i així successivament, triant el camí dret o esquerre, segons que n sigui parell o imparell a_n – 1 vegades. Per exemple, 2/5 = [0;2,2] es troba prenent el camí esquerre dues vegades i el camí dret una vegada.

L'arbre també està relacionat amb la successió de Farey. Suposem que es comença amb els punts extrems 0/1 i 1/1 en lloc de 0/1 i 1/0. En aquest cas, l'arbre contindrà tots els nombres racionals entre 0 i 1, inclusivament. Això no obstant, un recorregut en inordre d'aquest arbre fins a una profunditat ${\displaystyle n}$ no dona com a resultat la successió de Farey ${\displaystyle {\mathfrak {F}}_{n}}$. Això és degut al fet que per a ${\displaystyle n>1}$, la mediant de dos elements adjacents de ${\displaystyle {\mathfrak {F}}_{n-1}}$ s'insereix entre elles en ${\displaystyle {\mathfrak {F}}_{n}}$ només si el denominador de la nova fracció seria igual a ${\displaystyle n}$. En particular, la part de l'arbre de Stern-Brocot que comença amb 0/1 i 1/1 i arriba fins al nivell n, inclusivament, té ${\displaystyle 1+2^{n}}$ elements, mentre que la ${\displaystyle {\mathfrak {F}}_{n}}$ que inclou 0/1 i 1/1 conté només ${\displaystyle 1+\sum _{k=1}^{n}\phi (k)}$ elements.

Fraccions egipcianes i l'arbre de Stern-Brocot

Substituint cada fracció a/b de l'arbre per la fracció 1/ab, apareixen exemples d'aplicació de la fórmula de Fibonacci per a expansió de fraccions unitàries en fraccions egipcianes

${\displaystyle {\frac {1}{a}}={\frac {1}{(a+1)}}+{\frac {1}{a(a+1)}}\,}$

A partir de les fraccions 1/2, 1/3 i 2/3, per exemple, s'obté

${\displaystyle {\frac {1}{2}}={\frac {1}{3}}+{\frac {1}{6}}}$

Amb 1/3, 1/4 i 3/4,

${\displaystyle {\frac {1}{3}}={\frac {1}{4}}+{\frac {1}{12}}}$

Finalment, de 2/3, 2/5 i 3/5,

${\displaystyle {\frac {1}{6}}={\frac {1}{10}}+{\frac {1}{15}}}$

Enllaços externs

• MathWorld: Stern-Brocot tree

• PlanetMath: Stern-Brocot tree Arxivat 2008-06-20 a Wayback Machine.

• Stern-Brocot tree a cut-the-knot