Albero di Calkin-Wilf

L'albero di Calkin–Wilf

Come ogni valore è ricavato a partire dal valore precedente

Nella teoria dei numeri, l'albero di Calkin–Wilf è un albero in cui i vertici corrispondono uno a uno ai numeri razionali positivi . L'albero è radicato al numero 1 e ogni vertice è un numero razionale espresso come frazione irriducibile ${\displaystyle a \over b}$ che ha come vertici discendenti i numeri ${\displaystyle a \over a+b}$ e ${\displaystyle a+b \over b}$. Ogni numero razionale positivo compare esattamente una volta come nodo dell'albero. Esso prende il nome da Neil Calkin e Herbert Wilf, anche se appare in altre opere come il trattato Harmonices Mundi di Keplero.

La sequenza dei numeri razionali secondo l'ordine di visita in ampiezza dell'albero di Calkin-Wilf è nota come sequenza di Calkin-Wilf. La corrispondente sequenza dei numeratori (o, sfalsata di uno, dei denominatori) è la Serie Diatomica di Stern e può essere calcolata dalla funzione fusc.