Ir al contenido

Árbol de Calkin-Wilf

De Wikipedia, la enciclopedia libre
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

[editar]
El árbol representado en el Harmonices mundi (1619) de Kepler

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

[editar]
El árbol de Calkin–Wilf, dibujado utilzando el diseño de un árbol H

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/ba; si es a/b > 1, el padre de a/b es ab/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

[editar]
La secuencia de Calkin-Wilf, representada como la espiral roja trazaza a través del árbol de Calkin-Wilf

La secuencia de Calkin-Wilf es la secuencia de números racionales generados 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 qi denota el número i-ésimo en la secuencia, a partir de q1 = 1, y qi representa la parte entera.[7]

También es posible calcular qi 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 qi. Por ejemplo:

i = 1081 = 100001110012: La fracción continua es [1;2,3,4,1] por lo tanto q1081 = 53/37.
i = 1990 = 111110001102: La fracción continua es [0;1,2,3,5] por lo tanto q1990 = 37/53.

En la otra dirección, usar la fracción continua de cualquier qi como la codificación de longitud de ejecución de un número binario devuelve el mismo i. Por ejemplo:

qi = 3/4: la fracción continua es [0;1,3] por lo tanto i = 11102 = 14.
qi = 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 = 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

[editar]
Diagrama de dispersión de fusc(0...4096)

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

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 (nr
r
)
, 0 ≤ 2r < 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 2n 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 2n + 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

[editar]

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

[editar]
  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.
  5. a b 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).
  12. Bates, Bunder y Tognetti, 2010.

Bibliografía

[editar]

Enlaces externos

[editar]