Arbre de Calkin-Wilf

En teoria de números, el arbre de Calkin-Wilf és un tipo d'arbre en el que els vèrtiços corresponen un a un en els número racional positius. L'arbre té la seua raïl en el número 1, i qualsevol número racional expressat en térmens més simples com una Fracció de la forma $Plantilla:Sfrac$ té com dos fills als números $Plantilla:Sfrac$ i $Plantilla:Sfrac$ . Cada número racional positiu apareix exactament una volta en l'arbre. Du el nom de Neil Calkin i Herbert Wilf, pero apareix en atres treballs anteriors, inclós el Harmonices mundi de Johannes Kepler.

La seqüència d'número racional en un recorregut primer en esgambi de l'arbre de Calkin-Wilf es coneix com a seqüència de Calkin-Wilf. La seua seqüència de numeradors (o, desplaçats per un, denominadors) és la série diatómica de Stern, i pot calcular-se per mig de la funció fusc.

Història

L'arbre de Calkin-Wilf du el nom de Neil Calkin i d'Herbert Wilf, els qui ho varen considerar en un artícul de l'any 2000. En anterioritat, en un artícul de 1997, Jean Berstel i Aldo de Luca^[1] varen cridar al mateix arbre arbre de Raney, ya que varen amprar algunes idees extretes d'un artícul de 1973 de George N. Raney.^[2] La série diatómica de Stern va ser formulada molt abans per Moritz Abraham Stern, un matemàtic alemà de el XIX que també va idear l'estretament relacionat arbre de Stern-Brocot. Inclús abans, un arbre similar (que inclou solament les fraccions entre 0 i 1) apareix en l'obra Harmonices mundi (1619) de Johannes Kepler.^[3]

Definició i estructura

L'arbre de Calkin-Wilf es pot definir com un grafo dirigit en el que cada número racional positiu $Plantilla:Sfrac$ apareix com un vèrtiç i té una aresta eixint cap a un atre vèrtiç, el seu pare, llevat la raïl de l'arbre, el número 1, que no té pare.

El pare de qualsevol número racional es pot determinar despuix de posar el número en térmens més simples, com una fracció $Plantilla:Sfrac$ per a la qual el màxim comú divisor de $a$ i $b$ és 1. Si $Plantilla:Sfrac < 1$ , el pare de $Plantilla:Sfrac$ és $Plantilla:Sfrac$ ; si és $Plantilla:Sfrac > 1$ , el pare de $Plantilla:Sfrac$ és $Plantilla:Sfrac$ . Per lo tant, en qualsevol cas, el pare és una fracció en una suma més chicoteta de numerador i denominador, per lo que la reducció repetida d'este tipo finalment deu aplegar al número 1. Com un gràfic en una aresta eixint per vèrtiç i una raïl alcanzable per tots els demés vèrtiços, l'arbre Calkin-Wilf deu ser un arbre.

Els fills de qualsevol vèrtiç en l'arbre de Calkin-Wilf es poden calcular invertint la fòrmula dels pares d'un vèrtiç. Cada vèrtiç $Plantilla:Sfrac$ té un fill el valor del qual és menor que 1, $Plantilla:Sfrac$ , per supost $a + b > a$ . De manera similar, cada vèrtiç $Plantilla:Sfrac$ té un fill el valor del qual és major que 1, $Plantilla:Sfrac$ .^[4]

Com cada vèrtiç té dos fills, l'arbre de Calkin-Wilf és un arbre binario. No obstant, no és un arbre binario de busca: la seua orde interior no coincidix en l'orde ordenat dels seus vèrtiços. No obstant, està estretament relacionat en un arbre de busca binaria diferent en el mateix conjunt de vèrtiços, l'arbre de Stern-Brocot: els vèrtiços en cada nivell dels dos arbres coincidixen i estan relacionats entre sí per una permutació d'inversió de bits.Plantilla:Sfnp

Referències

↑ Berstel y de Luca (1997), Section 6.
↑ Raney (1973).
↑ (1619).«Harmonices Mundi».III.
↑ La descripció ací és dual a la definició original de Calkin i Wilf, que comença definint la relació fill i deduïx la relació pare com a part d'una prova de que tot racional apareix una volta en l'arbre. Com es definix ací, tot racional apareix una volta per definició i, en canvi, el fet de que l'estructura resultant siga un arbre requerix una prova.

Bibliografia

.
(1964).«A problem in partitions related to the Números de Stirling».Bulletin of the American Mathematical Society.70(2)

275–278.doi:10.1090/S0002-9904-1964-11118-6..

(1982).«Selected Writings on Computing: A Personal Perspective».Springer Science+Business Mija.. EWD 570: Un eixercici per a Dr.R.M.Burstall, pp. 215–216, i cs.utexas.edu/users/EWD/ewd05xx/EWD578.PDF EWD 578: Més sobre la funció "fusc" (Una seqüela de EWD570), pp. 230–232, reimpressions de notes escrites originalment en 1976.
.
.

Referències

Este artícul conté una traducció derivada de «Árbol de Calkin-Wilf» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

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

[2] Raney (1973).

[3] (1619).«Harmonices Mundi».III.

[4] La descripció ací és dual a la definició original de Calkin i Wilf, que comença definint la relació fill i deduïx la relació pare com a part d'una prova de que tot racional apareix una volta en l'arbre. Com es definix ací, tot racional apareix una volta per definició i, en canvi, el fet de que l'estructura resultant siga un arbre requerix una prova.

[1]

[2]

[3]

[4]