Arbre de Stern-Brocot

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 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 sí.

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,a2,...,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 n no dóna com a resultat la successió de Farey \mathfrak F_n. Això és degut al fet que per a n>1, la mediant de dos elements adjacents de \mathfrak F_{n-1} s'insereix entre elles en \mathfrak F_n només si el denominador de la nova fracció seria igual a 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é 1 + 2^n elements, mentre que la \mathfrak F_n que inclou 0/1 i 1/1 conté només 1 + \sum_{k=1}^n \phi(k) elements.

Fraccions egipcianes i l'arbre de Stern-Brocot[modifica | modifica el codi]

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

\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é


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


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


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


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


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

Enllaços externs[modifica | modifica el codi]