Arbre de Calkin-Wilf

En teoria dels nombres, l'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ó a/b 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.

The Calkin–Wilf tree

How values are derived from their parent

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.

Història

L'arbre de les Harmonices Mundi de Kepler (1619)

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

The Calkin–Wilf tree, drawn using an H tree layout.

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.

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⁠.

La seqüència de Calkin-Wilf, representada com l'espiral vermella que travessa l'arbre Calkin-Wilf

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.

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, … (successió A002487 a l'OEIS).

Utilitzant la numeració en base zero, el valor nè de la seqüència és el valor fusc(n) de la funció fusc, anomenada segons l'aspecte ofuscant de la seqüència de valors i definit per les relacions de recurrència.

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

amb els casos bàsics fusc(0) = 0 i fusc(1) = 1.

L'enèsim nombre racional en una travessa ample de l'arbre de Calkin-Wilf és el nombre fusc(n)/fusc(n + 1) ⁠. 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.