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](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/SternBrocotTree.svg/500px-SternBrocotTree.svg.png)
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 [a0;a1,a₂,...,an] s'obté començant al node 1/1 i triant el camí dret a0 vegades, després el camí esquerre a1 vegades, i així successivament, triant el camí dret o esquerre, segons que n sigui parell o imparell an – 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 no dona com a resultat la successió de Farey . Això és degut al fet que per a , la mediant de dos elements adjacents de s'insereix entre elles en només si el denominador de la nova fracció seria igual a . 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é elements, mentre que la que inclou 0/1 i 1/1 conté només 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
A partir de les fraccions 1/2, 1/3 i 2/3, per exemple, s'obté
Amb 1/3, 1/4 i 3/4,
Finalment, de 2/3, 2/5 i 3/5,
Enllaços externs
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png)
- MathWorld: Stern-Brocot tree
- PlanetMath: Stern-Brocot tree Arxivat 2008-06-20 a Wayback Machine.
- Stern-Brocot tree a cut-the-knot