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ó.

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 $n$ no dona 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

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