Utente:Colemarc/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 $a \over b$ che ha come vertici discendenti i numeri $a \over a+b$ e $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.

Storia

L'albero da Harmonices Mundi di Keplero (1619)

Neil Calkin e Herbert Wilf considerarono l'albero in un articolo del 2000. In un articolo del 1997, Jean Berstel e Aldo de Luca hanno chiamato il medesimo albero di Raney, poiché hanno tratto alcune idee da un articolo del 1973 di George N. Raney. La serie diatomica di Stern è stata formulata molto prima da Moritz Abraham Stern, un matematico tedesco del XIX secolo che ha anche inventato l'albero Stern-Brocot strettamente correlato. Ancor prima, un albero simile (che include solo le frazioni comprese tra 0 e 1) compariva nel trattato Harmonices Mundi di Keplero (1619).

Definizione e struttura

L'albero di Calkin-Wilf, disegnato utilizzando uno schema ad albero H.

L'albero di Calkin-Wilf può essere descritto come un grafo orientato in cui ogni numero razionale positivo $a \over b$ compare come vertice ed ha un arco che lo collega al vertice padre, fatta eccezione per il vertice radice, il numero 1, che non ha ascendenti.

L'ascendente di qualsiasi numero razionale può essere determinato dopo aver espresso il numero come frazione irriducibile $a \over b$, cioè tale che il massimo comune divisore di $a$ e $b$ è 1. Se ${a \over b}<1$, il genitore di ${a \over b}$ è ${a \over {b-a}}$; se ${a \over b}>1$, il genitore di $a \over b$ è $a-b \over b$. Pertanto, in entrambi i casi, il genitore è una frazione la cui somma di numeratore e denominatore è minore, quindi una riduzione ripetuta di questo tipo deve prima o poi raggiungere il numero 1.

I figli di qualsiasi vertice nell'albero di Calkin-Wilf possono essere calcolati invertendo la formula dei genitori di un vertice. Ogni vertice ${a \over b}$ ha un figlio $a \over a+b$ il cui valore è minore di 1, poiché questo è l'unico valore minore di 1 per il quale la formula dei genitori porta a ${a \over b}$. Analogamente, ogni vertice ${a \over b}$ ha un figlio $a+b \over b$ il cui valore è maggiore di 1.

Poiché ogni vertice ha due figli, l'albero di Calkin-Wilf è un albero binario. Tuttavia, non è un albero di ricerca binario : il suo ordine non coincide con l'ordine dei suoi vertici. Tuttavia, è strettamente correlato a un diverso albero di ricerca binario sullo stesso insieme di vertici, l'albero di Stern–Brocot: i vertici a ciascun livello dei due alberi coincidono e sono correlati tra loro da una permutazione di inversione di bit.

Attraversamento in ampiezza

La sequenza Calkin-Wilf, raffigurata come la spirale rossa che traccia attraverso l'albero di Calkin-Wilf

La sequenza Calkin–Wilf è la sequenza dei numeri razionali generati mediante un attraversamento in ampiezza dell'albero di Calkin–Wilf,

1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, ….

Poiché l'albero di Calkin-Wilf contiene ogni numero razionale positivo esattamente una volta, così fa questa sequenza. Il denominatore di ogni frazione è uguale al numeratore della frazione successiva nella sequenza. La sequenza Calkin-Wilf può anche essere generata direttamente dalla formula seguente:

$q_{i+1}={\frac {1}{2\lfloor q_{i}\rfloor -q_{i}+1}}$

dove $q_{i}$ denota lo i-esimo numero della sequenza, a partire da $q_{i}=1$, e $\lfloor q_{i}\rfloor$ rappresenta la parte intera.

È anche possibile calcolare $q_{i}$ direttamente dalla codifica run-length della rappresentazione binaria di $i$:

il numero di 1 consecutivi a partire dal bit meno significativo, quindi il numero di 0 consecutivi a partire dal primo blocco di 1, e così via. La sequenza di numeri generata in questo modo fornisce la rappresentazione come frazione continua di $q_{i}$. Esempio:

i = 1081 = 10000111001₂: La frazione continua è [1;2,3,4,1] quindi $q_{1081}={53 \over 37}$.

i = 1990 = 11111000110₂: La frazione continua è [0;1,2,3,5] quindi $q_{1990}={37 \over 53}$.

Viceversa, usando la frazione continua di qualsiasi $q_{i}$ come codifica run-length di un numero binario si ottiene $i$ stesso. Esempio:

$q_{i}={3 \over 4}$: La frazione continua è [0;1,3] quindi $i=1110_{2}=14$.

$q_{i}={4 \over 3}$: La frazione continua è [1;3]. Ma per usare questo metodo la lunghezza della frazione continua deve essere un numero pari. Pertanto [1;3] dovrebbe essere sostituita con la frazione continua equivalente [1;2,1]. Quindi $i=1001_{2}=9$.

Una conversione simile tra la codifica run-length di numeri binari e frazioni continue può essere utilizzata anche per valutare la funzione del punto interrogativo di Minkowski; tuttavia, nell'albero di Calkin-Wilf i numeri binari sono interi (posizioni dell'attraversamento in ampiezza) mentre nella funzione punto interrogativo sono numeri reali compresi tra 0 e 1.

Sequenza diatomica di Stern

Grafico a dispersione di fusc fusc(0...4096)

La sequenza diatomica di Stern è la sequenza intera

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, … (EN) Sequenza A002487, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation.

Utilizzando la numerazione che parte da zero, l'n-esimo valore nella sequenza è il valore $\operatorname {fusc} (n)$ della funzione fusc, denominata in base all'aspetto offuscato della sequenza di valori e definita dalle relazioni di ricorrenza

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

con i casi base $\operatorname {fusc} (0)=0$ e $\operatorname {fusc} (1)=1$.

L'n-esimo numero razionale in una traversata in ampiezza dell'albero di Calkin-Wilf è il numero $\operatorname {fusc} (0) \over \operatorname {fusc} (n+1)$. Pertanto la sequenza diatomica corrisponde sia alla sequenza dei numeratori che alla sequenza dei denominatori dei numeri della sequenza di Calkin–Wilf.

La funzione $\operatorname {fusc} (n+1)$ è il numero di coefficienti binomiali dispari della forma ${\binom {n-r}{r}},\ 0\leq 2r\leq n$, e conta anche il numero di modi di scrivere $n$ come somma di potenze di due in cui ciascuna potenza compare al massimo due volte. Questo può essere visto nella ricorrenza che definisce fusc: le espressioni come somma di potenze di due per un numero pari 2n o non hanno 1 in esse (nel qual caso sono formate raddoppiando ogni termine in un'espressione per n) o due 1 (in tal caso il resto dell'espressione è formato raddoppiando ogni termine in un'espressione per n−1), quindi il numero di rappresentazioni è la somma del numero di rappresentazioni per n e per n−1, corrispondente alla ricorrenza. Allo stesso modo, ogni rappresentazione per un numero dispari 2n+1 è formata raddoppiando una rappresentazione per n e aggiungendo 1, sempre facendo corrispondere la ricorrenza. Per esempio,

6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1

ha tre rappresentazioni come somma di potenze di due con al massimo due copie di ciascuna potenza, quindi $\operatorname {fusc} (6+1)=3$.

Relazione con l'albero di Stern–Brocot

L'albero di Calkin-Wilf assomiglia all'albero di Stern-Brocot in quanto entrambi sono alberi binari con ogni numero razionale positivo che appare esattamente una volta. Inoltre, i livelli superiori dei due alberi appaiono molto simili e in entrambi gli alberi gli stessi numeri appaiono agli stessi livelli. Un albero può essere ottenuto dall'altro eseguendo una permutazione di inversione di bit sui numeri a ciascun livello degli alberi. In alternativa, il numero in un dato nodo dell'albero di Calkin–Wilf può essere convertito nel numero nella stessa posizione nell'albero di Stern–Brocot, e viceversa, mediante un processo che implica l'inversione delle rappresentazioni della frazione continua di questi numeri. Tuttavia questi alberi hanno proprietà diverse: ad esempio, l'albero di Stern–Brocot è un albero di ricerca binario: l'ordine di attraversamento da sinistra a destra dell'albero è lo stesso dell'ordine numerico dei numeri in esso. Questa proprietà non vale per l'albero di Calkin-Wilf.