Ver el código de «Árbol de Calkin-Wilf»

{{multiple image|image1=Calkin–Wilf tree.svg|caption1=El árbol de Calkin–Wilf|width1=300|image2=Calkin-Wilf tree children from parent.gif|caption2=Modo en que se calculan los valores a partir de sus ''padres''|width2=175}}

En [[teoría de números]], el '''árbol de Calkin-Wilf''' es un tipo de [[Árbol (teoría de grafos)|árbol]] en el que los [[Vértice (teoría de grafos)|vértices]] corresponden [[Función biyectiva|uno a uno]] con los [[números racionales]] [[Signo (matemáticas)|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 {{math|{{sfrac|''a''|''b''}}}} tiene como dos ''hijos'' a los números {{math|{{sfrac|''a''|''a'' + ''b''}}}} y {{math|{{sfrac|''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 [[Búsqueda en anchura|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==
[[Archivo:Kepler Tree-original.jpg|thumb|upright=1.35|El árbol representado en el ''[[Harmonices mundi]]'' (1619) de [[Johannes Kepler|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<ref>{{harvtxt|Berstel|de Luca|1997}}, Section 6.</ref> llamaron al mismo árbol ''árbol de Raney'', ya que emplearon algunas ideas extraídas de un artículo de 1973 de George N. Raney.<ref>{{harvtxt|Raney|1973}}.</ref> La serie diatómica de Stern fue formulada mucho antes por [[Moritz Abraham Stern]], un matemático alemán del {{siglo|XIX||s}} 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]].<ref>{{citation|first=J.|last=Kepler|authorlink=Johannes Kepler|title=Harmonices Mundi|volume=III|page=27|url=https://archive.org/stream/ioanniskepplerih00kepl#page/26/mode/2up|year=1619}}.</ref>

==Definición y estructura==
[[File:Calkin-Wilf tree.svg|thumb|upright=1.8|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 {{math|{{sfrac|''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 {{math|{{sfrac|''a''|''b''}}}} para la cual el [[máximo común divisor]] de {{math|''a''}} y {{math|''b''}} es 1. Si {{math|{{sfrac|''a''|''b''}} < 1}}, el padre de {{math|{{sfrac|''a''|''b''}}}} es {{math|{{sfrac|''a''|''b'' − ''a''}}}}; si es {{math|{{sfrac|''a''|''b''}} > 1}}, el padre de {{math|{{sfrac|''a''|''b''}}}} es {{math|{{sfrac|''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 {{math|{{sfrac|''a''|''b''}}}} tiene un hijo cuyo valor es menor que 1, {{math|{{sfrac|''a''|''a'' + ''b''}}}}, por supuesto {{math|''a'' + ''b'' > ''a''}}. De manera similar, cada vértice {{math|{{sfrac|''a''|''b''}}}} tiene un hijo cuyo valor es mayor que 1, {{math|{{sfrac|''a'' + ''b''|''b''}}}}.<ref>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.</ref>

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]].{{sfnp|Gibbons|Lester|Bird|2006}}

==Amplitud del primer recorrido==
[[File:Calkin-Wilf spiral.svg|thumb|upright=1.2|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,
:{{sfrac|1|1}}, {{sfrac|1|2}}, {{sfrac|2|1}}, {{sfrac|1|3}}, {{sfrac|3|2}}, {{sfrac|2|3}}, {{sfrac|3|1}}, {{sfrac|1|4}}, {{sfrac|4|3}}, {{sfrac|3|5}}, {{sfrac|5|2}}, {{sfrac|2|5}}, {{sfrac|5|3}}, {{sfrac|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.<ref>{{harvtxt|Calkin|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 {{sfrac|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." {{harvtxt|Gibbons|Lester|Bird|2006}} analizaron técnicas eficientes de [[programación funcional]] para realizar este recorrido en amplitud.</ref> 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

:<math>q_{i+1}= \frac{1}{2\lfloor q_i\rfloor - q_i + 1}</math>

donde {{math|''q<sub>i</sub>''}} denota el número {{math|''i''}}-ésimo en la secuencia, a partir de {{math|''q''<sub>1</sub> {{=}} 1}}, y {{math|⌊ ''q<sub>i</sub>'' ⌋}} representa la [[Funciones de parte entera|parte entera]].<ref>{{harvtxt|Aigner|Ziegler|2004}} acreditó esta fórmula a Moshe Newman.</ref>

También es posible calcular {{math|''q<sub>i</sub>''}} directamente mediante [[run-length encoding|codificación de longitud de ejecución]] [[sistema binario|binaria]] de {{mvar|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 {{math|''q<sub>i</sub>''}}. Por ejemplo:

:i = 1081 = 10000111001<sub>2</sub>: La fracción continua es [1;2,3,4,1] por lo tanto {{math|''q''<sub>1081</sub> {{=}} {{sfrac|53|37}}}}.
:i = 1990 = 11111000110<sub>2</sub>: La fracción continua es [0;1,2,3,5] por lo tanto {{math|''q''<sub>1990</sub> {{=}} {{sfrac|37|53}}}}.

En la otra dirección, usar la fracción continua de cualquier {{math|''q<sub>i</sub>''}} como la codificación de longitud de ejecución de un número binario devuelve el mismo {{mvar|i}}. Por ejemplo:

:{{math|''q<sub>i</sub>'' {{=}} {{sfrac|3|4}}}}: la [[fracción continua]] es [0;1,3] por lo tanto {{mvar|i}} = 1110<sub>2</sub> = 14.
:{{math|''q<sub>i</sub>'' {{=}} {{sfrac|4|3}}}}: la [[fracción continua]] es [1;3]. Pero para usar este método, la longitud de la fracción continua debe ser [[números pares e impares|impar]]. Entonces [1;3] debe ser reemplazado por la fracción continua equivalente [1;2,1]. Por lo tanto {{mvar|i}} = 1001<sub>2</sub> = 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==
[[File:Fusc plot 4096.svg|thumb|upright=1.5|[[Diagrama de dispersión]] de {{math|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, … {{OEIS|id=A002487}}.

Usando [[numeración en base 0]], el valor {{math|''n''}}-ésimo en la secuencia es el valor {{math|fusc(''n'')}} de la '''función fusc''', denominada<ref>El nombre fusc fue dado en 1976 por [[Edsger Dijkstra]]; véase EWD570 y EWD578.</ref> de acuerdo con la apariencia ofuscante de la secuencia de valores y definida por la [[relación de recurrencia]]

:<math>\begin{align}
\operatorname{fusc}(2n) &= \operatorname{fusc}(n) \\
\operatorname{fusc}(2n+1) &= \operatorname{fusc}(n) + \operatorname{fusc}(n+1),
\end{align}</math>

con los casos base {{math|fusc(0) {{=}} 0}} y {{math|fusc(1) {{=}} 1}}.

El {{math|''n''}}-ésimo número racional en un primer recorrido transversal del árbol de Calkin-Wilf es el número {{math|{{sfrac|fusc(''n'')|fusc(''n'' + 1)}}}}.<ref>{{harvtxt|Calkin|Wilf|2000}}, Theorem 1.</ref> 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 {{math|fusc(''n'' + 1)}} es el número de [[coeficiente binomial]] impares de la forma {{math|({{su|p=''n'' − ''r''|b=''r''|a=c}})}}, {{math|0 ≤ 2''r'' < ''n''}},<ref>{{harvtxt|Carlitz|1964}}.</ref> y también cuenta el número de formas de escribir {{math|''n''}} como una suma de [[Potencia de dos|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 {{math|2''n''}} no tienen 1 (en cuyo caso se forman duplicando cada término en una expresión para {{math|''n''}}) o dos 1 (en cuyo caso el resto de la expresión se forma duplicando cada término en una expresión para {{math|''n'' − 1}}), por lo que el número de representaciones es la suma del número de representaciones para {{math|''n''}} y para {{math|''n'' − 1}}, coincidiendo con la recurrencia. De manera similar, cada representación de un número impar {{math|2''n'' + 1}} se forma duplicando una representación de {{math|''n''}} y sumando 1, igualando nuevamente la recurrencia.<ref>La entrada de la OEIS acredita este hecho a {{harvtxt|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 {{math|fusc(''n'')}} en lugar de por {{math|fusc(''n'' + 1)}}. {{math|fusc(''n'' + 1)}}.</ref> Por ejemplo,
:6 = 4&nbsp;+&nbsp;2 = 4&nbsp;+&nbsp;1&nbsp;+&nbsp;1 = 2&nbsp;+&nbsp;2&nbsp;+&nbsp;1&nbsp;+&nbsp;1
tiene tres representaciones como una suma de potencias de dos con como máximo dos copias de cada potencia, por lo que {{math|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.{{sfnp|Gibbons|Lester|Bird|2006}} 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.{{sfnp|Bates|Bunder|Tognetti|2010}}

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==
{{listaref}}

==Bibliografía==
*{{citation
|last1= Aigner|first1= Martin|author1-link= Martin Aigner
|last2= Ziegler|first2= Günter M.|author2-link= Günter M. Ziegler
|edition= 3rd
|isbn= 978-3-540-40460-6
|location= Berlin; New York
|publisher= Springer
|title= [[ Proofs from THE BOOK]]
|pages= 94–97
|year= 2004}}
*{{citation
|last1= Bates|first1= Bruce
|last2= Bunder|first2= Martin
|last3= Tognetti|first3= Keith
|doi= 10.1016/j.ejc.2010.04.002
|issue= 7
|journal= European Journal of Combinatorics
|mr= 2673006
|pages= 1637–1661
|title= Linking the Calkin-Wilf and Stern-Brocot trees
|volume= 31
|year= 2010|url= https://ro.uow.edu.au/infopapers/2586
 }}
*{{citation
|last1= Berstel|first1= Jean
|last2= de Luca|first2= Aldo
|year= 1997
|title= Sturmian words, Lyndon words and trees
|journal= [[Theoretical Computer Science]]
|volume= 178
|issue= 1–2
|pages= 171–203
|doi= 10.1016/S0304-3975(96)00101-6}}
*{{citation
|last1= Calkin|first1= Neil
|last2= Wilf|first2= Herbert|author2-link= Herbert Wilf
|issue= 4
|journal= [[American Mathematical Monthly]]
|pages= 360–363
|title= Recounting the rationals
|url= http://www.math.upenn.edu/~wilf/website/recounting.pdf
|volume= 107
|year= 2000
|doi= 10.2307/2589182
|publisher= [[Mathematical Association of America]]
|jstor= 2589182}}.
*{{citation|first=L.|last=Carlitz|authorlink=Leonard Carlitz|title=A problem in partitions related to the [[Números de Stirling]]|journal=[[ Bulletin of the American Mathematical Society]]|volume=70|issue=2|year=1964|pages=275–278|mr=0157907|doi=10.1090/S0002-9904-1964-11118-6}}.
*{{citation|first=Edsger W.|last=Dijkstra|authorlink=Edsger W. Dijkstra|title=Selected Writings on Computing: A Personal Perspective|publisher=[[Springer Science+Business Media]]|year=1982|isbn=0-387-90652-5|url=https://archive.org/details/selectedwritings0000dijk}}. [http://www.cs.utexas.edu/users/EWD/ewd05xx/EWD570.PDF EWD 570: Un ejercicio para Dr.R.M.Burstall], pp.&nbsp;215–216, y [http://www. cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF EWD 578: Más sobre la función "fusc" (Una secuela de EWD570)], pp.&nbsp;230–232, reimpresiones de notas escritas originalmente en 1976.
*{{citation
|last1= Gibbons|first1= Jeremy|authorlink1= Jeremy Gibbons
|last2= Lester|first2= David
|last3= Bird|first3= Richard|author3-link= Richard Bird (computer scientist)
|doi= 10.1017/S0956796806005880
|issue= 3
|journal= [[ Journal of Functional Programming]]
|pages= 281–291
|title= Functional pearl: Enumerating the rationals
|volume= 16
|year= 2006}}.
*{{citation
|last= Raney|first= George N.
|year= 1973
|title= On continued fractions and finite automata
|journal= [[Mathematische Annalen]]
|volume= 206
|issue= 4
|pages= 265–283
|doi= 10.1007/BF01355980|hdl= 10338.dmlcz/128216
|s2cid= 120933574
|hdl-access= free
 }}
*{{citation
|last= Stern|first= Moritz A.|author-link= Moritz Abraham Stern
|journal= [[Crelle (revista)|Journal für die reine und angewandte Mathematik]]
|pages= 193–220
|title= Ueber eine zahlentheoretische Funktion
|url= http://www.digizeitschriften.de/resolveppn/GDZPPN002150301
|volume= 55
|year= 1858}}.

==Enlaces externos==
*{{mathworld|urlname=Calkin-WilfTree|title=Calkin–Wilf Tree|mode=cs2}}
*{{mathworld|urlname=SternsDiatomicSeries|title=Stern's Diatomic Series|mode=cs2}}
*{{citation|url=http://www.cut-the-knot.org/blue/Fusc.shtml|title=Fractions on a Binary Tree II|publisher=[[Alexander Bogomolny]]|first=Alexander|last=Bogomolny|authorlink= Alexander Bogomolny}}

{{Control de autoridades}}
{{DEFAULTSORT:arbol de Calkin-Wilf}}
[[Categoría:Sucesiones de números enteros]]
[[Categoría:Árboles (estructura)]]