En teoría de números , el árbol de Calkin-Wilf es un árbol en el que los vértices corresponden uno a uno a 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 la fracción a/B tiene como sus dos hijos los números a/a + b y a + b/B. Cada número racional positivo aparece exactamente una vez en el árbol.
La secuencia de números racionales en un recorrido en amplitud del árbol de Calkin-Wilf se conoce como secuencia de Calkin-Wilf . Su secuencia de numeradores (o, compensada por uno, denominadores) es la serie diatómica de Stern y puede calcularse mediante la función fusc .
El árbol Calkin-Wilf lleva el nombre de Neil Calkin y Herbert Wilf , quienes lo consideraron en su artículo de 2000. El árbol fue presentado anteriormente por Jean Berstel y Aldo de Luca [1] como árbol de Raney , ya que extrajeron algunas ideas de un artículo 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 siglo XIX que también inventó el árbol Stern-Brocot, estrechamente relacionado . Incluso antes, un árbol similar aparece en Harmonices Mundi de Kepler (1619). [3]
Definición y estructura
El árbol de Calkin-Wilf se puede definir como un gráfico dirigido en el que cada número racional positivoa/Bocurre como un vértice y tiene un borde saliente a otro vértice, su padre. Asumimos quea/Bestá en los términos más simples; es decir, el máximo común divisor de un y b es 1. Sia/B<1 , el padre dea/B es a/b - a; Sia/B> 1 , el padre dea/B es a - b/B. 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 debe eventualmente alcanzar el número 1. Como un gráfico con un borde saliente por vértice y una raíz alcanzable por todos los demás vértices , el árbol de Calkin-Wilf debe ser un árbol.
Los hijos de cualquier vértice del árbol de Calkin-Wilf se pueden calcular invirtiendo la fórmula de los padres de un vértice. Cada vérticea/B tiene un hijo cuyo valor es menor que 1, a/a + b, porque este es el único valor menor que 1 cuya fórmula principal conduce a a/B. Del mismo modo, cada vérticea/B tiene un hijo cuyo valor es mayor que 1, a + b/B. [4]
Aunque es un árbol binario (cada vértice tiene dos hijos), el árbol de Calkin-Wilf no es un árbol de búsqueda binario : su orden no coincide con el orden de sus vértices. Sin embargo, está estrechamente relacionado con un árbol de búsqueda binario 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í mediante una permutación de inversión de bits . [5]
Ancho primer recorrido
La secuencia de Calkin-Wilf es la secuencia de números racionales generada por un recorrido en anchura del árbol de Calkin-Wilf,
- 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4,….
Debido a que el árbol de Calkin-Wilf contiene cada número racional positivo exactamente una vez, también lo hace esta secuencia. [6] 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 q i denota el i- ésimo número en la secuencia, comenzando desde q 1 = 1 , y ⌊ q i ⌋ representa la parte integral . [7]
También es posible calcular q i directamente a partir de la codificación de longitud de ejecución de la representación binaria de i : el número de unos consecutivos a partir del bit menos significativo, luego el número de ceros consecutivos a partir del primer bloque de unos, y así sucesivamente. . La secuencia de números generada de esta manera da la representación de fracción continua de q i. Ejemplo:
- i = 1081 = 10000111001 2 : La fracción continua es [1; 2,3,4,1] por tanto q 1081 = 53/37.
- i = 1990 = 11111000110 2 : La fracción continua es [0; 1,2,3,5] por tanto q 1990 = 37/53.
En la otra dirección, usar la fracción continua de cualquier q i como la codificación de longitud de ejecución de un número binario devuelve i mismo. Ejemplo:
- q yo = 3/4: La fracción continua es [0; 1,3] por tanto i = 1110 2 = 14.
- q yo = 4/3: La fracción continua es [1; 3]. Pero para usar este método, la longitud de la fracción continua debe ser un número impar . Por tanto, [1; 3] debe sustituirse por la fracción continua equivalente [1; 2,1]. Por tanto, i = 1001 2 = 9.
También se puede utilizar una conversión similar entre números binarios codificados por longitud de ejecución y fracciones continuas para evaluar la función del signo de interrogación de Minkowski ; sin embargo, en el árbol de Calkin-Wilf, los números binarios son números enteros (posiciones en el recorrido transversal primero en amplitud) 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 secuencia entera
Utilizando la numeración basada en cero , el n- ésimo valor de la secuencia es el valor fusc ( n ) de la función fusc , denominada [8] de acuerdo con la apariencia confusa de la secuencia de valores y definida por las relaciones de recurrencia
con los casos base fusc (0) = 0 y fusc (1) = 1 .
El n- ésimo número racional en un recorrido en anchura del árbol de Calkin-Wilf es el númerofusc ( n )/fusc ( n + 1). [9] 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 fusc ( n + 1) es el número de coeficientes binomiales impares de la forma (n - r
r) ,0 ≤ 2 r < n , [10] y también cuenta el número de formas de escribir n como una suma depotencias de dosen las que cada potencia ocurre como máximo dos veces. Esto se puede ver en la recurrencia que define fusc: las expresiones como una suma de potencias de dos para un número par2 n no tienen 1 (en cuyo caso se forman al duplicar cada término en una expresión para n ) o dos 1s (en cuyo caso el resto de la expresión se forma duplicando cada término en una expresión para n - 1), por lo que el número de representaciones es la suma del número de representaciones para n y para n - 1, coincidiendo con la recurrencia. De manera similar, cada representación de un número impar2 n + 1se forma duplicando una representación de ny sumando 1, de nuevo haciendo coincidir la recurrencia. [11] Por ejemplo,
- 6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1
tiene tres representaciones como una suma de potencias de dos con un máximo de dos copias de cada potencia, por lo que fusc (6 + 1) = 3 .
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 una permutación de inversión de bits en los números en cada nivel de los árboles. [5] 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 de Stern-Brocot, y viceversa, mediante un proceso que implica la inversión de las representaciones de fracciones continuas de estos números. [12] Sin embargo, de otras formas, tienen propiedades diferentes: por ejemplo, el árbol de Stern-Brocot es un árbol de búsqueda binario : el orden transversal de izquierda a derecha del árbol es el mismo que el orden numérico de los números en eso. Esta propiedad no es cierta para el árbol de Calkin-Wilf.
Notas
- ^ Berstel y de Luca (1997) , Sección 6.
- ^ Raney (1973) .
- ↑ Kepler, J. (1619), Harmonices Mundi , III , p. 27.
- ^ La descripción aquí es dual con la definición original de Calkin y Wilf, que comienza definiendo la relación del niño y deriva la relación del padre como parte de una prueba de que cada racional aparece una vez en el árbol. Como se define aquí, cada racional aparece una vez por definición y, en cambio, el hecho de que la estructura resultante sea un árbol requiere una prueba.
- ↑ a b Gibbons, Lester y Bird (2006) .
- ^ Calkin y Wilf (2000) : "se puede hacer una lista de todos los números racionales positivos, cada uno de los cuales aparece una y sólo una vez, escribiendo 1/1, 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. " Gibbons, Lester & Bird (2006) discuten la eficiencia funcional técnicas de programación para realizar este primer recorrido de amplitud.
- ^ Aigner y Ziegler (2004) atribuyen esta fórmula a Moshe Newman.
- ↑ El nombre fusc fue dado en 1976 por Edsger W. Dijkstra ; consulte EWD570 y EWD578.
- ^ Calkin y Wilf (2000) , Teorema 1.
- ^ Carlitz (1964) .
- ↑ La entrada de la OEIS atribuye este hecho a Carlitz (1964) 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 fusc ( n ) en lugar de por fusc ( n + 1) .
- ^ Bates, Bunder y Tognetti (2010) .
Referencias
- Aigner, Martin ; Ziegler, Günter M. (2004), Proofs from THE BOOK (3ª ed.), Berlín; Nueva York: Springer, págs. 94–97, ISBN 978-3-540-40460-6
- Bates, Bruce; Bunder, Martin; Tognetti, Keith (2010), "Linking the Calkin-Wilf and Stern-Brocot trees" , European Journal of Combinatorics , 31 (7): 1637–1661, doi : 10.1016 / j.ejc.2010.04.002 , MR 2673006
- Berstel, Jean; de Luca, Aldo (1997), "Sturmian words, Lyndon words and trees", Theoretical Computer Science , 178 (1–2): 171–203, doi : 10.1016 / S0304-3975 (96) 00101-6
- Calkin, Neil; Wilf, Herbert (2000), "Recounting the rationals" (PDF) , American Mathematical Monthly , Mathematical Association of America , 107 (4): 360–363, doi : 10.2307 / 2589182 , JSTOR 2589182.
- Carlitz, L. (1964), "Un problema en las particiones relacionadas con los números de Stirling ", Boletín de la American Mathematical Society , 70 (2): 275-278, doi : 10.1090 / S0002-9904-1964-11118-6 , Señor 0157907.
- Dijkstra, Edsger W. (1982), Escritos seleccionados sobre informática: una perspectiva personal , Springer-Verlag , ISBN 0-387-90652-5. EWD 570: Un ejercicio para Dr.RMBurstall , págs. 215-216, y EWD 578: Más sobre la función "fusc" (Una secuela de EWD570) , págs. 230-232, reimpresiones de notas escritas originalmente en 1976.
- Gibbons, Jeremy ; Lester, David; Bird, Richard (2006), "Perla funcional: enumerando los racionales", Journal of Functional Programming , 16 (3): 281-291, doi : 10.1017 / S0956796806005880.
- Raney, George N. (1973), "Sobre fracciones continuas y autómatas finitos", Mathematische Annalen , 206 (4): 265-283, doi : 10.1007 / BF01355980 , hdl : 10338.dmlcz / 128216 , S2CID 120933574
- Stern, Moritz A. (1858), "Ueber eine zahlentheoretische Funktion" , Journal für die reine und angewandte Mathematik , 55 : 193-220.
enlaces externos
- Weisstein, Eric W. "Árbol de Calkin-Wilf" . MathWorld .
- Weisstein, Eric W. "Serie diatómica de Stern" . MathWorld .
- Bogomolny, Alexander , Fracciones en un árbol binario II , Cortar el nudo