Vés al contingut

Arbre de Stern-Brocot

De la Viquipèdia, l'enciclopèdia lliure

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
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 [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

[modifica]

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

[modifica]