Árbol de Calkin-Wilf
En teoría de números, el árbol de Calkin-Wilf es un tipo de árbol en el que los vértices corresponden uno a uno con los números racionales positivos. El árbol tiene su raíz en el número 1, y cualquier número racional expresado en términos más simples como una Fracción de la forma Plantilla:Math tiene como dos hijos a los números Plantilla:Math y Plantilla:Math. Cada número racional positivo aparece exactamente una vez en el árbol. Lleva el nombre de Neil Calkin y Herbert Wilf, pero aparece en otros trabajos anteriores, incluido el Harmonices mundi de Johannes Kepler.
La secuencia de números racionales en un recorrido primero en anchura del árbol de Calkin-Wilf se conoce como secuencia de Calkin-Wilf. Su secuencia de numeradores (o, desplazados por uno, denominadores) es la serie diatómica de Stern, y puede calcularse mediante la función fusc.
Historia
El árbol de Calkin-Wilf lleva el nombre de Neil Calkin y de Herbert Wilf, quienes lo consideraron en un artículo del año 2000. Con anterioridad, en un artículo de 1997, Jean Berstel y Aldo de Luca[1] llamaron al mismo árbol árbol de Raney, ya que emplearon algunas ideas extraídas de un artículo de 1973 de George N. Raney.[2] La serie diatómica de Stern fue formulada mucho antes por Moritz Abraham Stern, un matemático alemán del Plantilla:Siglo que también ideó el estrechamente relacionado árbol de Stern-Brocot. Incluso antes, un árbol similar (que incluye solo las fracciones entre 0 y 1) aparece en la obra Harmonices mundi (1619) de Johannes Kepler.[3]
Definición y estructura
El árbol de Calkin-Wilf se puede definir como un grafo dirigido en el que cada número racional positivo Plantilla:Math aparece como un vértice y tiene una arista saliente hacia otro vértice, su padre, excepto la raíz del árbol, el número 1, que no tiene padre.
El padre de cualquier número racional se puede determinar después de poner el número en términos más simples, como una fracción Plantilla:Math para la cual el máximo común divisor de Plantilla:Math y Plantilla:Math es 1. Si Plantilla:Math, el padre de Plantilla:Math es Plantilla:Math; si es Plantilla:Math, el padre de Plantilla:Math es Plantilla:Math. Por lo tanto, en cualquier caso, el padre es una fracción con una suma más pequeña de numerador y denominador, por lo que la reducción repetida de este tipo finalmente debe llegar al número 1. Como un gráfico con una arista saliente por vértice y una raíz alcanzable por todos los demás vértices, el árbol Calkin-Wilf debe ser un árbol.
Los hijos de cualquier vértice en el árbol de Calkin-Wilf se pueden calcular invirtiendo la fórmula de los padres de un vértice. Cada vértice Plantilla:Math tiene un hijo cuyo valor es menor que 1, Plantilla:Math, por supuesto Plantilla:Math. De manera similar, cada vértice Plantilla:Math tiene un hijo cuyo valor es mayor que 1, Plantilla:Math.[4]
Como cada vértice tiene dos hijos, el árbol de Calkin-Wilf es un árbol binario. Sin embargo, no es un árbol binario de búsqueda: su orden interior no coincide con el orden ordenado de sus vértices. Sin embargo, está estrechamente relacionado con un árbol de búsqueda binaria diferente en el mismo conjunto de vértices, el árbol de Stern-Brocot: los vértices en cada nivel de los dos árboles coinciden y están relacionados entre sí por una permutación de inversión de bits.Plantilla:Sfnp
Amplitud del primer recorrido
La secuencia de Calkin-Wilf es la secuencia de números racionales generados por un recorrido en anchura del árbol de Calkin-Wilf,
- Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, Plantilla:Sfrac, ….
Debido a que el árbol de Calkin-Wilf contiene cada número racional positivo exactamente una vez, también lo hace esta secuencia.[5] El denominador de cada fracción es igual al numerador de la siguiente fracción en la secuencia. La secuencia de Calkin-Wilf también se puede generar directamente mediante la fórmula
donde Plantilla:Math denota el número Plantilla:Math-ésimo en la secuencia, a partir de Plantilla:Math, y Plantilla:Math representa la parte entera.[6]
También es posible calcular Plantilla:Math directamente mediante codificación de longitud de ejecución binaria de Plantilla:Mvar: el número de 1 consecutivos a partir del bit menos significativo, luego el número de 0 consecutivos a partir del primer bloque de 1, y así sucesivamente. La secuencia de números generada de esta manera da la representación en forma de fracción continua de Plantilla:Math. Por ejemplo:
- i = 1081 = 100001110012: La fracción continua es [1;2,3,4,1] por lo tanto Plantilla:Math.
- i = 1990 = 111110001102: La fracción continua es [0;1,2,3,5] por lo tanto Plantilla:Math.
En la otra dirección, usar la fracción continua de cualquier Plantilla:Math como la codificación de longitud de ejecución de un número binario devuelve el mismo Plantilla:Mvar. Por ejemplo:
- Plantilla:Math: la fracción continua es [0;1,3] por lo tanto Plantilla:Mvar = 11102 = 14.
- Plantilla:Math: la fracción continua es [1;3]. Pero para usar este método, la longitud de la fracción continua debe ser impar. Entonces [1;3] debe ser reemplazado por la fracción continua equivalente [1;2,1]. Por lo tanto Plantilla:Mvar = 10012 = 9.
También se puede usar una conversión similar entre números binarios codificados por longitud de ejecución y fracciones continuas para evaluar la función interrogación de Minkowski. Sin embargo, en el árbol de Calkin-Wilf los números binarios son números enteros (posiciones en el recorrido primero en anchura) mientras que en la función de signo de interrogación son números reales entre 0 y 1.
Secuencia diatómica de Stern
La secuencia diatómica de Stern es la sucesión entera
- 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, … Plantilla:OEIS.
Usando numeración en base 0, el valor Plantilla:Math-ésimo en la secuencia es el valor Plantilla:Math de la función fusc, denominada[7] de acuerdo con la apariencia ofuscante de la secuencia de valores y definida por la relación de recurrencia
con los casos base Plantilla:Math y Plantilla:Math.
El Plantilla:Math-ésimo número racional en un primer recorrido transversal del árbol de Calkin-Wilf es el número Plantilla:Math.[8] Por lo tanto, la secuencia diatómica forma tanto la secuencia de numeradores como la secuencia de denominadores de los números en la secuencia de Calkin-Wilf.
La función Plantilla:Math es el número de coeficiente binomial impares de la forma Plantilla:Math, Plantilla:Math,[9] y también cuenta el número de formas de escribir Plantilla:Math como una suma de powers of two en la que cada potencia aparece como máximo dos veces. Esto se puede ver en el fusc que define la recurrencia: las expresiones como una suma de potencias de dos para un número par Plantilla:Math no tienen 1 (en cuyo caso se forman duplicando cada término en una expresión para Plantilla:Math) o dos 1 (en cuyo caso el resto de la expresión se forma duplicando cada término en una expresión para Plantilla:Math), por lo que el número de representaciones es la suma del número de representaciones para Plantilla:Math y para Plantilla:Math, coincidiendo con la recurrencia. De manera similar, cada representación de un número impar Plantilla:Math se forma duplicando una representación de Plantilla:Math y sumando 1, igualando nuevamente la recurrencia.[10] Por ejemplo,
- 6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1
tiene tres representaciones como una suma de potencias de dos con como máximo dos copias de cada potencia, por lo que Plantilla:Math.
Relación con el árbol de Stern-Brocot
El árbol de Calkin-Wilf se parece al árbol de Stern-Brocot en que ambos son árboles binarios y cada número racional positivo aparece exactamente una vez. Además, los niveles superiores de los dos árboles parecen muy similares, y en ambos árboles los mismos números aparecen en los mismos niveles. Se puede obtener un árbol del otro realizando un permutación de inversión de bits en los números en cada nivel de los árboles.Plantilla:Sfnp Alternativamente, el número en un nodo dado del árbol de Calkin-Wilf se puede convertir en el número en la misma posición en el árbol Stern-Brocot, y viceversa, mediante un proceso que involucra la inversión de las representaciones mediante una fracción continua de estos números.Plantilla:Sfnp
Sin embargo, en otros aspectos, tienen propiedades diferentes: por ejemplo, el árbol de Stern-Brocot es un árbol binario de búsqueda: el orden de recorrido de izquierda a derecha del árbol es el mismo que el orden numérico de los números que contiene. Esta propiedad no es cierta para el árbol de Calkin-Wilf.
Referencias
Bibliografía
- Plantilla:Citation
- Plantilla:Citation
- Plantilla:Citation
- Plantilla:Citation.
- Plantilla:Citation.
- Plantilla:Citation. EWD 570: Un ejercicio para Dr.R.M.Burstall, pp. 215–216, y cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF EWD 578: Más sobre la función "fusc" (Una secuela de EWD570), pp. 230–232, reimpresiones de notas escritas originalmente en 1976.
- Plantilla:Citation.
- Plantilla:Citation
- Plantilla:Citation.
Enlaces externos
Plantilla:Control de autoridades
- ↑ Plantilla:Harvtxt, Section 6.
- ↑ Plantilla:Harvtxt.
- ↑ Plantilla:Citation.
- ↑ La descripción aquí es dual a la definición original de Calkin y Wilf, que comienza definiendo la relación hijo y deduce la relación padre como parte de una prueba de que todo racional aparece una vez en el árbol. Como se define aquí, todo racional aparece una vez por definición y, en cambio, el hecho de que la estructura resultante sea un árbol requiere una prueba.
- ↑ Plantilla:Harvtxt: "se puede hacer una lista de todos los números racionales positivos, cada uno de los cuales aparece una y solo una vez, escribiendo Plantilla:Sfrac, luego las fracciones en el nivel justo debajo de la parte superior del árbol, leyendo de izquierda a derecha , luego las fracciones en el siguiente nivel hacia abajo, leyendo de izquierda a derecha, etc." Plantilla:Harvtxt analizaron técnicas eficientes de programación funcional para realizar este recorrido en amplitud.
- ↑ Plantilla:Harvtxt acreditó esta fórmula a Moshe Newman.
- ↑ El nombre fusc fue dado en 1976 por Edsger Dijkstra; véase EWD570 y EWD578.
- ↑ Plantilla:Harvtxt, Theorem 1.
- ↑ Plantilla:Harvtxt.
- ↑ La entrada de la OEIS acredita este hecho a Plantilla:Harvtxt y al trabajo no citado de Lind. Sin embargo, el artículo de Carlitz describe una clase más restringida de sumas de potencias de dos, contadas por Plantilla:Math en lugar de por Plantilla:Math. Plantilla:Math.