Mostra la font per a Arbre de Calkin-Wilf

{{Imatge múltiple|image1=Calkin–Wilf tree.svg|caption1=The Calkin–Wilf tree|width1=300|image2=Calkin-Wilf tree children from parent.gif|caption2=How values are derived from their parent|width2=175}}

En [[Teoria de nombres|teoria dels nombres]], l{{'}}'''arbre de Calkin-Wilf''' és un [[Arbre (teoria de grafs)|arbre]] en què els [[Vèrtex (teoria de grafs)|vèrtexs]] corresponen [[Funció bijectiva|un a un]] amb els [[Nombre racional|nombres racionals]] [[Signe (matemàtiques)|positius]]. L'arbre té l'arrel al número 1, i qualsevol nombre racional s'expressa en termes més simples com a [[fracció]] {{math|{{sfrac|''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.<ref>{{Ref-web|títol=Continued fractions - Algorithms for Competitive Programming|url=https://cp-algorithms.com/algebra/continued-fractions.html|consulta=2024-08-04|llengua=anglès}}</ref>

La seqüència de nombres racionals en una [[Cerca en amplada|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'''.<ref>{{Ref-web|url=file:///home/rai/Downloads/The%20Calkin%20Wilf%20Tree%20Extensions%20and%20Applications%20Final.pdf|títol=The Calkin-Wilf Tree:
Extensions and Applications|consulta=4-8-2024|llengua=anglès}}</ref>

== Història ==
[[Fitxer:Kepler_Tree-original.jpg|miniatura|L'arbre de ''[[Harmonices Mundi|les Harmonices Mundi]]'' [[Johannes Kepler|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 de Stern-Brocot|arbre Stern-Brocot]] molt relacionat. Fins i tot abans, un arbre semblant (incloent només les fraccions entre 0 i 1) apareix a ''[[Harmonices Mundi|les Harmonices Mundi]]'' [[Johannes Kepler|de Kepler]] (1619).

== Definició i estructura ==
[[Fitxer:Calkin-Wilf_tree.svg|enllaç=https://en.wikipedia.org/wiki/File:Calkin-Wilf_tree.svg|miniatura|The Calkin–Wilf tree, drawn using an [[:en:H_tree|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.<ref>{{Ref-web|títol=Calkin-Wilf Tree|url=https://mathworld.wolfram.com/|consulta=2024-08-04|llengua=en|nom=Eric W.|cognom=Weisstein}}</ref>

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⁠.
[[Fitxer:Calkin-Wilf_spiral.svg|miniatura|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 binari de cerca|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 de Stern-Brocot|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]]. {{Sfnb|Gibbons|Lester|Bird|2006}}

== Seqüència diatòmica d'Stern ==
'''La seqüència diatòmica de Stern''' és la [[Seqüència d'enters|seqüència entera]]

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, … {{OEIS|id=A002487}}.

Utilitzant [[Numeració en base zero|la numeració en base zero]], el valor {{Math|''n''}}è de la seqüència és el valor {{Math|fusc(''n'')}} de la '''funció fusc''', anomenada <ref>The fusc name was given in 1976 by [[Edsger W. Dijkstra]]; see EWD570 and EWD578.</ref> segons l'aspecte ofuscant de la seqüència de valors i definit per les [[Relació de recurrència|relacions de recurrència.]]

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

amb els casos bàsics {{Math|fusc(0) {{=}} 0}} i {{Math|fusc(1) {{=}} 1}}.

L'enèsim nombre racional en una travessa ample de l'arbre de Calkin-Wilf és el nombre {{math|{{sfrac|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.

== Referències ==
{{Referències}}

[[Categoria:Seqüències d'enters]]