Albero di Calkin–Wilf

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.

L'albero di Calkin–Wilf

Come ogni valore è ricavato a partire dal valore precedente

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 è un albero binario infinito in cui ogni ad ogni vertice è associato un numero razionale positivo espresso come frazione irriducibile $a \over b$; in particolare, al vertice radice è associato il numero $1 \over 1$. Ciascun vertice $a \over b$ possiede un figlio a sinistra il cui valore è $a \over a+b$ ed un figlio a destra il cui valore è $a+b \over b$.

• Osservazione 1: Ogni vertice ha un figlio a sinistra il cui valore è minore di 1, dato che $a<a+b$. Analogamente, ogni vertice ha un figlio a destra il cui valore è maggiore di 1.
• Osservazione 2: La somma di numeratore e denominatore del primo figlio è $2a+b$, mentre quella del secondo figlio è $a+2b$; in entrambi i casi la somma è maggiore di quella del genitore $a+b$. Ne consegue che percorrendo l'albero in discesa si ottiene sempre una sequenza di somme strettamente crescente. Al contrario, risalendo l'albero si ottiene sempre una sequenza di somme strettamente decrescente.

Il genitore di qualsiasi numero razionale può essere determinato dopo aver espresso il numero come frazione irriducibile $p \over q$, cioè tale che il massimo comune divisore di $p$ e $q$ è 1. Se ${p \over q}<1$, il genitore di $p \over q$ è ${p \over {q-p}}$; se ${p \over q}>1$, il genitore di $p \over q$ è $p-q \over q$. Pertanto, il genitore è una frazione la cui somma di numeratore e denominatore è $p$ oppure $q$, ed in entrambi i casi è minore di $p+q$, che è la somma corrispondente alla frazione $p \over q$. Ne consegue che una riduzione ripetuta di questo tipo deve prima o poi raggiungere la frazione irriducibile con somma minima, cioè il numero $1 \over 1$. Questa è una prova informale del fatto che ogni numero razionale compare almeno una volta come vertice dell'albero.

Inoltre, la formula del genitore fornisce ad ogni passo un valore di somma univoco e inferiore al precedente, quindi, dato un numero razionale qualsiasi, la sequenza di somme per risalire dal vertice associato fino alla radice è unica e strettamente decrescente (come già evidenziato sopra). A causa della struttura propria dei grafi ad albero, se – per assurdo – vi fossero due vertici distinti con lo stesso numero razionale, risalendo l'albero da ciascuno si arriverebbe prima o poi allo stesso vertice. Dato che la sequenza di somme è strettamente decrescente, il numero di passi compiuti per arrivare a questo vertice da ciascuno dei due vertici di partenza deve essere lo stesso, altrimenti avremmo due valori somma distinti per lo stesso vertice. In altre parole le due sequenze di somme, oltre che uguali, sono anche sincronizzate. Ne consegue che i due figli del vertice in comune (che corrispondono al passo precedente della sequenza) hanno lo stesso valore somma, il che è in contraddizione con la definizione dell'albero. La conclusione è che non possono esistere due vertici con lo stesso numero razionale, ovvero che un determinato numero razionale può comparire al più una volta nell'albero. Nel complesso quindi, ogni numero razionale compare esattamente una volta nell'albero in forma di frazione irriducibile.

Poiché ogni vertice ha due figli, l'albero di Calkin-Wilf è un albero binario, ma non è un albero di ricerca binario poiché 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 che si trovano 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,

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

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su albero di Calkin–Wilf

Collegamenti esterni

• (EN) Eric W. Weisstein, Albero di Calkin–Wilf, su MathWorld, Wolfram Research.
• Alexander Bogomolny, Fractions on a Binary Tree II, Cut-the-knot.