En teoría de números , el árbol de Stern-Brocot es un árbol binario completo infinito en el que los vértices corresponden uno por uno a los números racionales positivos , cuyos valores están ordenados de izquierda a derecha como en un árbol de búsqueda .
El árbol Stern-Brocot fue descubierto independientemente por Moritz Stern ( 1858 ) y Achille Brocot ( 1861 ). Stern era un teórico de números alemán; Brocot era un relojero francés que utilizó el árbol Stern-Brocot para diseñar sistemas de engranajes con una relación de transmisión cercana a algún valor deseado al encontrar una relación de números suaves cerca de ese valor.
La raíz del árbol Stern-Brocot corresponde al número 1. La relación padre-hijo entre los números en el árbol Stern-Brocot puede definirse en términos de fracciones continuas o mediantes , y un camino en el árbol desde la raíz a cualquier otro. número q proporciona una secuencia de aproximaciones a q con pequeños denominadores que q . Debido a que el árbol contiene cada número racional positivo exactamente una vez, una primera búsqueda en amplitud del árbol proporciona un método para enumerar todos los racionales positivos que está estrechamente relacionado con las secuencias de Farey . El subárbol izquierdo del árbol de Stern-Brocot, que contiene los números racionales en el rango (0,1), se llama árbol de Farey .
Un árbol de fracciones continuas
Todo número racional positivo q puede expresarse como una fracción continua de la forma
donde k y un 0 son números enteros no negativos, y cada coeficiente subsiguiente una i es un entero positivo. Esta representación no es única porque uno tiene
para cada secuencia de coeficientes a 0 , ..., a k −1 . Usando esta identidad para reescribir cualquier representación de la primera forma en la última forma, se puede obtener que el coeficiente final satisfaga a k ≥ 2 (a menos que k = 0 , en cuyo caso se obtiene un 0 ≥ 1); con este requisito adicional, la representación se vuelve única. Entonces, a menos que q = 1 , el número q tiene un padre en el árbol de Stern-Brocot dado por la expresión de fracción continua
que en el caso de a k = 2 se puede reescribir como. Por ejemplo, el número racional 23 ⁄ 16 tiene la representación de fracción continua
por lo que su padre en el árbol Stern-Brocot es el número
Este padre se forma disminuyendo el denominador en el término más interno de la fracción continua en 1, y contrayéndose con el término anterior si la fracción se convierte en .
A la inversa, cada número q en el árbol de Stern-Brocot tiene exactamente dos hijos: si
entonces un niño es el número representado por la fracción continua
mientras que el otro niño está representado por la fracción continua
Uno de estos niños es menor que q y este es el niño izquierdo; el otro es mayor que q y es el hijo derecho (de hecho, la expresión anterior da el hijo izquierdo si k es impar, y el hijo derecho si k es par). Por ejemplo, la representación de fracción continua de 13 ⁄ 9 es [1; 2,4] y sus dos hijos son [1; 2,5] = 16 ⁄ 11 (el niño correcto) y [1; 2,3,2] = 23 ⁄ 16 (el hijo izquierdo).
Está claro que para cada expresión de fracción continua finita, uno puede moverse repetidamente a su padre y llegar a la raíz [1;] = 1 ⁄ 1 del árbol en un número finito de pasos (en un 0 + ... + un k - 1 pasos para ser precisos). Por lo tanto, cada número racional positivo aparece exactamente una vez en este árbol. Además, todos los descendientes del hijo izquierdo de cualquier número q son menores que q , y todos los descendientes del hijo derecho de q son mayores que q . Los números en la profundidad d en el árbol son los números para los cuales la suma de los coeficientes de fracción continua es d + 1 .
Mediantes y búsqueda binaria
El árbol de Stern-Brocot forma un árbol de búsqueda binario infinito con respecto al orden habitual de los números racionales. [1] [2] El conjunto de números racionales que descienden de un nodo q se define por el intervalo abierto ( L q , H q ) donde L q es el antepasado de q que es más pequeño que q y más cercano a él en el árbol ( o L q = 0 si q no tiene un ancestro más pequeño) mientras que H q es el ancestro de q que es más grande que q y más cercano a él en el árbol (o H q = + ∞ si q no tiene un ancestro más grande).
La ruta desde la raíz 1 hasta un número q en el árbol de Stern-Brocot se puede encontrar mediante un algoritmo de búsqueda binaria , que se puede expresar de forma sencilla utilizando mediantes . Aumente los números racionales no negativos para incluir un valor 1/0 (que representa + ∞) que es, por definición, mayor que todos los demás racionales. El algoritmo de búsqueda binaria procede de la siguiente manera:
- Inicialice dos valores L y H a 0/1 y 1/0, respectivamente.
- Hasta que se encuentre q , repita los siguientes pasos:
- Deje que L = un / b y H = c / d ; calcule la mediante M = ( a + c ) / ( b + d ).
- Si M es menor que q , entonces q está en el intervalo abierto ( M , H ); reemplace L por M y continúe.
- Si M es mayor que q , entonces q está en el intervalo abierto ( L , M ); reemplace H por M y continúe.
- En el caso restante, q = M ; terminar el algoritmo de búsqueda.
La secuencia de valores M calculada por esta búsqueda es exactamente la secuencia de valores en la ruta desde la raíz hasta q en el árbol de Stern-Brocot. Cada intervalo abierto ( L , H ) que se produce en algún paso en la búsqueda es el intervalo ( L M , H M ) que representa los descendientes de la mediant M . El padre de q en el árbol de Stern-Brocot es el último mediante encontrado que no es igual a q .
Este procedimiento de búsqueda binaria se puede utilizar para convertir números de punto flotante en números racionales. Al detenerse una vez que se alcanza la precisión deseada, los números de punto flotante se pueden aproximar con precisión arbitraria. [3] Si un número real x se aproxima por cualquier número racional a / b que no esté en la secuencia de mediantes encontrada por el algoritmo anterior, entonces la secuencia de mediantes contiene una aproximación más cercana ax que tiene un denominador como máximo igual a b ; en ese sentido, estos mediants forman las mejores aproximaciones racionales a x .
El árbol de Stern-Brocot puede definirse directamente en términos de mediantes: el hijo izquierdo de cualquier número q es el mediante de q con su antepasado más cercano más pequeño, y el hijo derecho de q es el mediante de q con su antepasado más cercano más grande. En esta fórmula, qy su ancestro deben tomarse en términos más bajos, y si no hay un ancestro más pequeño o más grande, entonces 0/1 o 1/0 deben usarse respectivamente. Nuevamente, usando 7/5 como ejemplo, su antepasado más pequeño más cercano es 4/3, por lo que su hijo izquierdo es (4 + 7) / (3 + 5) = 11/8, y su antepasado más grande más cercano es 3/2, por lo que su hijo derecho es (7 + 3) / (5 + 2) = 10/7.
Relación con las secuencias de Farey
La secuencia de Farey de orden n es la secuencia ordenada de fracciones en el intervalo cerrado [0,1] que tienen un denominador menor o igual que n . Como en la técnica de búsqueda binaria para generar el árbol de Stern-Brocot, las secuencias de Farey se pueden construir usando mediantes: la secuencia de Farey de orden n + 1 se forma a partir de la secuencia de Farey de orden n calculando la mediante de cada dos valores consecutivos en la secuencia de Farey de orden n , manteniendo el subconjunto de mediants que tienen denominador exactamente igual al n + 1, y la colocación de estos mediants entre los dos valores de la que fueron calculados.
También se puede ver un proceso similar de inserción mediante, que comienza con un par diferente de puntos finales de intervalo [0 / 1,1 / 0], para describir la construcción de los vértices en cada nivel del árbol de Stern-Brocot. La secuencia Stern-Brocot de orden 0 es la secuencia [0 / 1,1 / 0], y la secuencia Stern-Brocot de orden i es la secuencia formada al insertar un mediante entre cada par consecutivo de valores en la secuencia Stern-Brocot de orden i - 1. La secuencia Stern-Brocot de orden i consta de todos los valores en los primeros i niveles del árbol Stern-Brocot, junto con los valores límite 0/1 y 1/0, en orden numérico.
Por lo tanto, las secuencias de Stern-Brocot difieren de las secuencias de Farey de dos maneras: eventualmente incluyen todos los racionales positivos, no solo los racionales dentro del intervalo [0,1], y en el n- ésimo paso se incluyen todos los mediantes, no solo los con denominador igual an . La secuencia de Farey de orden n se puede encontrar mediante un recorrido en orden del subárbol izquierdo del árbol de Stern-Brocot, retrocediendo siempre que se alcanza un número con denominador mayor que n .
Propiedades adicionales
Si son todos los racionales a la misma profundidad en el árbol Stern-Brocot, entonces
- .
Además, si son dos fracciones consecutivas en o por encima de un cierto nivel en el árbol (en el sentido de que cualquier fracción entre ellas, debe estar en un nivel inferior del árbol), entonces
- . [4]
Junto con las definiciones en términos de fracciones continuas y mediantes descritas anteriormente, el árbol de Stern-Brocot también puede definirse como un árbol cartesiano para los números racionales, priorizados por sus denominadores. En otras palabras, es el árbol de búsqueda binario único de los números racionales en el que el padre de cualquier vértice q tiene un denominador menor que q (o si q y su padre son ambos enteros, en el que el padre es menor que q ). Se desprende de la teoría de los árboles cartesianas que el ancestro común más bajo de cualquier dos números q y r en el árbol de Stern-Brocot es el número racional en el intervalo cerrado [ q , r ] que tiene el denominador más pequeño entre todos los números en este intervalo .
Permutar los vértices en cada nivel del árbol de Stern-Brocot mediante una permutación de inversión de bits produce un árbol diferente, el árbol de Calkin-Wilf , en el que los hijos de cada número a / b son los dos números a / ( a + b ) y ( a + b ) / b . Como el árbol de Stern-Brocot, el árbol de Calkin-Wilf contiene cada número racional positivo exactamente una vez, pero no es un árbol de búsqueda binario.
Ver también
- Función de signo de interrogación de Minkowski , cuya definición de argumentos racionales está estrechamente relacionada con el árbol de Stern-Brocot.
- Árbol de Calkin-Wilf
Notas
- ^ Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994), Matemáticas concretas (Segunda ed.), Addison-Wesley, págs. 116-118, ISBN 0-201-55802-5
- ^ Gibbons, Jeremy; Lester, David; Bird, Richard (2006), "Perla funcional: enumerando los racionales", Journal of Functional Programming , 16 (3): 281-291, doi : 10.1017 / S0956796806005880.
- ^ Sedgewick y Wayne, Introducción a la programación en Java . Puede encontrar una implementación Java de este algoritmo aquí .
- ↑ Bogomolny atribuye esta propiedad a Pierre Lamothe, un teórico de la música canadiense.
Referencias
- Brocot, Achille (1861), "Calcul des rouages par Approximation, nouvelle méthode", Revue Chronométrique , 3 : 186-194.
- Stern, Moritz A. (1858), "Ueber eine zahlentheoretische Funktion" , Journal für die reine und angewandte Mathematik , 55 : 193-220.
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009), Combinatoria sobre palabras. Palabras de Christoffel y repeticiones en palabras , CRM Monograph Series, 27 , Providence, RI: American Mathematical Society , ISBN 978-0-8218-4480-9, Zbl 1161.68043
enlaces externos
- Aiylam, Dhroova, secuencias de Stern-Brocot modificadas , arXiv : 1301.6807 , código bibliográfico : 2013arXiv1301.6807A
- Austin, David, Árboles, dientes y tiempo: las matemáticas de la fabricación de relojes , columna de características de la AMS
- Bogomolny, Alexander , Stern Brocot-Tree , cut-the-knot , consultado el 3 de septiembre de 2008.
- Sloane, NJA , The Stern-Brocot o Farey Tree , Enciclopedia en línea de secuencias de enteros.
- Wildberger, Norman, MF96: Fracciones y el árbol Stern-Brocot.
- Weisstein, Eric W. "Stern-Brocot Tree" . MathWorld .
- Árbol de Stern-Brocot en PlanetMath .
- Fracciones infinitas , Numberphile
- Amazing Graphs III , Numberphile
- Secuencia OEIS A002487 (serie diatómica de Stern (o secuencia Stern-Brocot))