Arbre de Calkin-Wilf
En teoria dels nombres, lPlantilla:'arbre de Calkin-Wilf és un arbre en què els vèrtexs corresponen un a un amb els nombres racionals positius. L'arbre té l'arrel al número 1, i qualsevol nombre racional s'expressa en termes més simples com a fracció Plantilla:Math té com a dos fills els números a/a + b i a + b/b. Cada nombre racional positiu apareix exactament una vegada a l'arbre. Porta el nom de Neil Calkin i Herbert Wilf, però apareix en altres obres, com ara Harmonices Mundi de Kepler.[1]
La seqüència de nombres racionals en una travessa ample de l'arbre de Calkin-Wilf es coneix com la seqüència de Calkin-Wilf. La seva seqüència de numeradors (o, compensats per un, denominadors) és la sèrie diatòmica de Stern, i es pot calcular mitjançant la funció fusc.[2]
Història
L'arbre Calkin-Wilf rep el nom de Neil Calkin i Herbert Wilf, que el van considerar en un article de l'any 2000. En un article de 1997, Jean Berstel i Aldo de Luca van anomenar el mateix arbre l' arbre de Raney, ja que van extreure algunes idees d'un article de 1973 de George N. Raney. La sèrie diatòmica de Stern va ser formulada molt abans per Moritz Abraham Stern, un matemàtic alemany del segle XIX que també va inventar l'arbre Stern-Brocot molt relacionat. Fins i tot abans, un arbre semblant (incloent només les fraccions entre 0 i 1) apareix a les Harmonices Mundi de Kepler (1619).
Definició i estructura
L'arbre de Calkin-Wilf es pot definir com un gràfic dirigit en el qual cada nombre racional positiu a/b apareix com a vèrtex i té una aresta sortint a un altre vèrtex, el seu pare, excepte l'arrel de l'arbre, el número 1, que no té pares.[3]
El pare de qualsevol nombre racional es pot determinar després de posar el nombre en els termes més simples, com una fracció a/b per a la qual el màxim comú divisor d'a i b és 1. Si a/b < 1, el pare de a/b és a/b − a; si a/b > 1, el pare de a/b és a − b/b. Així, en qualsevol dels casos, el pare és una fracció amb una suma més petita de numerador i denominador, de manera que la reducció repetida d'aquest tipus ha d'arribar finalment al número 1. Com a gràfic amb una aresta sortint per vèrtex i una arrel accessible per tots els altres vèrtexs, l'arbre de Calkin-Wilf a de ser realment un arbre.
Els fills de qualsevol vèrtex de l'arbre de Calkin-Wilf es poden calcular invertint la fórmula dels pares d'un vèrtex. Cada vèrtex a/b té un fill el valor del qual és inferior a 1, a/a + b, perquè, per descomptat, a + b > a. De la mateixa manera, cada vèrtex a/b té un fill el valor del qual és superior a 1, a + b/b.
Com que cada vèrtex té dos fills, l'arbre Calkin-Wilf és un arbre binari. Tanmateix, no és un arbre de cerca binari: el seu inordre no coincideix amb l'ordre ordenat dels seus vèrtexs. No obstant això, està estretament relacionat amb un arbre de cerca binari diferent al mateix conjunt de vèrtexs, l'arbre Stern-Brocot: els vèrtexs a cada nivell dels dos arbres coincideixen i estan relacionats entre si per una permutació de inversió de bits. Plantilla:Sfnb
Seqüència diatòmica d'Stern
La seqüència diatòmica de Stern és la seqüència entera
0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, … Plantilla:OEIS.
Utilitzant la numeració en base zero, el valor Plantilla:Mathè de la seqüència és el valor Plantilla:Math de la funció fusc, anomenada [4] segons l'aspecte ofuscant de la seqüència de valors i definit per les relacions de recurrència.
amb els casos bàsics Plantilla:Math i Plantilla:Math.
L'enèsim nombre racional en una travessa ample de l'arbre de Calkin-Wilf és el nombre Plantilla:Math . Així, la seqüència diatòmica forma tant la seqüència de numeradors com la seqüència de denominadors dels nombres de la seqüència de Calkin-Wilf.
Referències
- ↑ Plantilla:Ref-web
- ↑ Plantilla:Ref-web
- ↑ Plantilla:Ref-web
- ↑ The fusc name was given in 1976 by Edsger W. Dijkstra; see EWD570 and EWD578.