Árbol de Calkin-Wilf

El árbol de Calkin–Wilf

Modo en que se calculan los valores a partir de sus padres

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 $a / b$ tiene como dos hijos a los números $a / a + b$ y $a + b / b$ . 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 siglo XIX 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 $a / b$ 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 $a / b$ para la cual el máximo común divisor de $a$ y $b$ es 1. Si $a / b < 1$ , el padre de $a / b$ es $a / b - a$ ; si es $a / b > 1$ , el padre de $a / 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 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 $a / b$ tiene un hijo cuyo valor es menor que 1, $a / a + b$ , por supuesto $a + b > a$ . De manera similar, cada vértice $a / b$ tiene un hijo cuyo valor es mayor que 1, $a + b / b$ .^[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.^[5]

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,

11, 12, 21, 13, 32, 23, 31, 14, 43, 35, 52, 25, 53, 34, ….

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

q_{i+1}={\frac {1}{2\lfloor q_{i}\rfloor -q_{i}+1}}

donde $q i$ denota el número $i$ -ésimo en la secuencia, a partir de $q 1 = 1$ , y $⌊ q i ⌋$ representa la parte entera.^[7]

También es posible calcular $q i$ directamente mediante codificación de longitud de ejecución binaria de $i$ : 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 $q i$ . Por ejemplo:

i = 1081 = 10000111001₂: La fracción continua es [1;2,3,4,1] por lo tanto

q 1081 = 53 / 37

.

i = 1990 = 11111000110₂: La fracción continua es [0;1,2,3,5] por lo 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 el mismo $i$ . Por ejemplo:

q i = 3 / 4

: la fracción continua es [0;1,3] por lo tanto

i

= 1110₂ = 14.

q i = 4 / 3

: 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

i

= 1001₂ = 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, … (sucesión A002487 en OEIS).

Usando numeración en base 0, el valor $n$ -ésimo en la secuencia es el valor $fusc(n)$ de la función fusc, denominada^[8] de acuerdo con la apariencia ofuscante de la secuencia de valores y definida por la relación de recurrencia

{\begin{aligned}\operatorname {fusc} (2n)&=\operatorname {fusc} (n)\\\operatorname {fusc} (2n+1)&=\operatorname {fusc} (n)+\operatorname {fusc} (n+1),\end{aligned}}

con los casos base $fusc(0) = 0$ y $fusc(1) = 1$ .

El $n$ -ésimo número racional en un primer recorrido transversal del árbol de Calkin-Wilf es el número $fusc(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 coeficiente binomial impares de la forma $(n - r r)$ , $0 \leq 2 r < n$ ,^[10] y también cuenta el número de formas de escribir $n$ 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 $2 n$ no tienen 1 (en cuyo caso se forman duplicando cada término en una expresión para $n$ ) o dos 1 (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 impar $2 n + 1$ se forma duplicando una representación de $n$ y sumando 1, igualando nuevamente 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 como máximo 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 un 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 Stern-Brocot, y viceversa, mediante un proceso que involucra la inversión de las representaciones mediante una fracción continua de estos números.^[12]

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

↑ Berstel y de Luca (1997), Section 6.
↑ Raney (1973).
↑ Kepler, J. (1619), Harmonices Mundi III, p. 27 ..
↑ 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.
↑ ^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 solo 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 y Bird (2006) analizaron técnicas eficientes de programación funcional para realizar este recorrido en amplitud.
↑ Aigner y Ziegler (2004) acreditó esta fórmula a Moshe Newman.
↑ El nombre fusc fue dado en 1976 por Edsger Dijkstra; véase EWD570 y EWD578.
↑ Calkin y Wilf (2000), Theorem 1.
↑ Carlitz (1964).
↑ La entrada de la OEIS acredita 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)$ . $fusc(n + 1)$ .
↑ Bates, Bunder y Tognetti, 2010.

Bibliografía

Aigner, Martin; Ziegler, Günter M. (2004), Proofs from THE BOOK (3rd edición), Berlin; New York: Springer, pp. 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, MR 2673006, doi:10.1016/j.ejc.2010.04.002 .
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», American Mathematical Monthly (Mathematical Association of America) 107 (4): 360-363, JSTOR 2589182, doi:10.2307/2589182 ..
Carlitz, L. (1964), «A problem in partitions related to the Números de Stirling», Bulletin of the American Mathematical Society 70 (2): 275-278, MR 0157907, doi:10.1090/S0002-9904-1964-11118-6 ..
Dijkstra, Edsger W. (1982), Selected Writings on Computing: A Personal Perspective, Springer Science+Business Media, ISBN 0-387-90652-5 .. 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.
Gibbons, Jeremy; Lester, David; Bird, Richard (2006), «Functional pearl: Enumerating the rationals», Journal of Functional Programming 16 (3): 281-291, doi:10.1017/S0956796806005880 ..
Raney, George N. (1973), «On continued fractions and finite automata», Mathematische Annalen 206 (4): 265-283, S2CID 120933574, doi:10.1007/BF01355980, hdl:10338.dmlcz/128216 .
Stern, Moritz A. (1858), «Ueber eine zahlentheoretische Funktion», Journal für die reine und angewandte Mathematik 55: 193-220 ..

Enlaces externos

Weisstein, Eric W. «Calkin–Wilf Tree». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Weisstein, Eric W. «Stern's Diatomic Series». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Bogomolny, Alexander, Fractions on a Binary Tree II, Alexander Bogomolny .

Datos: Q4158811
Multimedia: Calkin–Wilf tree and sequence / Q4158811

[1] Berstel y de Luca (1997), Section 6.

[2] Raney (1973).

[3] Kepler, J. (1619), Harmonices Mundi III, p. 27 ..

[4] 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.

[FOOTNOTEGibbonsLesterBird2006-5] Gibbons, Lester y Bird, 2006.

[6] Calkin y Wilf (2000): "se puede hacer una lista de todos los números racionales positivos, cada uno de los cuales aparece una y solo 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 y Bird (2006) analizaron técnicas eficientes de programación funcional para realizar este recorrido en amplitud.

[7] Aigner y Ziegler (2004) acreditó esta fórmula a Moshe Newman.

[8] El nombre fusc fue dado en 1976 por Edsger Dijkstra; véase EWD570 y EWD578.

[9] Calkin y Wilf (2000), Theorem 1.

[10] Carlitz (1964).

[11] La entrada de la OEIS acredita 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)$ . $fusc(n + 1)$ .

[FOOTNOTEBatesBunderTognetti2010-12] Bates, Bunder y Tognetti, 2010.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]