Calkin–Wilf tree - Calkin–Wilf tree

L'albero di Calkin-Wilf

Come i valori sono derivati dal loro genitore

L'albero dalle Harmonices Mundi di Keplero (1619)

In 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 nel numero 1 e qualsiasi numero razionale espresso in termini più semplici come frazione $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} un/B$ ha come due figli i numeri $un / a + b$ e $a + b / B$ . Ogni numero razionale positivo appare esattamente una volta nell'albero.

La sequenza di numeri razionali in un attraversamento in ampiezza dell'albero di Calkin-Wilf è nota come sequenza di Calkin-Wilf . La sua sequenza di numeratori (o, spostati di uno, denominatori) è la serie biatomica di Stern e può essere calcolata dalla funzione fusc .

L'albero Calkin-Wilf prende il nome da Neil Calkin e Herbert Wilf , che lo considerarono nel loro articolo del 2000. L'albero è stato introdotto in precedenza da Jean Berstel e Aldo de Luca come albero di Raney , poiché hanno tratto alcune idee da un articolo di George N. Raney. La serie biatomica di Stern è stata formulata molto prima da Moritz Abraham Stern , un matematico tedesco del XIX secolo che inventò anche l' albero strettamente correlato Stern-Brocot . Ancor prima, un albero simile appare nelle Harmonices Mundi di Keplero (1619).

Definizione e struttura

L'albero Calkin-Wilf, disegnato utilizzando un layout ad albero H.

L'albero di Calkin-Wilf può essere definito come un grafo orientato in cui ogni numero razionale positivo $un / B$ si verifica come vertice e ha un arco in uscita da un altro vertice, il suo genitore. Supponiamo che $un / B$ è in termini più semplici; cioè, il massimo comun divisore di $a$ e $b$ è 1. Se $un / B < 1$ , il genitore di $un / B$ è $un / b - a$ ; Se $un / B > 1$ , il genitore di $un / B$ è $a - b / B$ . Quindi, in entrambi i casi, il genitore è una frazione con una somma minore di numeratore e denominatore, quindi una riduzione ripetuta di questo tipo deve alla fine raggiungere il numero 1. Come un grafo con un arco uscente per vertice e una radice raggiungibile da tutti gli altri vertici , l'albero Calkin-Wilf deve essere davvero un albero.

I figli di ogni vertice nell'albero di Calkin-Wilf possono essere calcolati invertendo la formula per i genitori di un vertice. ogni vertice $un / B$ ha un figlio il cui valore è inferiore a 1, $un / a + b$ , perché questo è l'unico valore minore di 1 la cui formula padre riconduce a $un / B$ . Allo stesso modo, ogni vertice $un / B$ ha un figlio il cui valore è maggiore di 1, $a + b / B$ .

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

Larghezza prima traversata

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

La sequenza di Calkin-Wilf è la sequenza di numeri razionali generati da un attraversamento in ampiezza dell'albero di Calkin-Wilf,

11, 12, 21, 13, 32, 23, 31, 14, 43, 35, 52, 25, 53, 34, ….

Poiché l'albero di Calkin-Wilf contiene ogni numero razionale positivo esattamente una volta, lo stesso vale per 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

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

dove $q i$ denota l' $i-$ esimo numero della sequenza, partendo da $q 1 = 1$ , e $⌊ q i ⌋$ rappresenta la parte integrale .

È 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 così generata fornisce la rappresentazione in frazione continua di $q i$ .Esempio:

i = 1081 = 100000111001 ₂ : La frazione continua è [1;2,3,4,1] quindi

q 1081 = 53 / 37

.

i = 1990 = 11111000110 ₂ : La frazione continua è [0;1,2,3,5] quindi

q 1990 = 37 / 53

.

Nell'altra direzione, l'uso della frazione continua di qualsiasi $q i$ come codifica della lunghezza di esecuzione di un numero binario restituisce $i$ stesso. Esempio:

q io = 3 / 4

: La frazione continua è [0;1,3] quindi

i

= 1110 ₂ = 14.

q io = 4 / 3

: La frazione continua è [1;3]. Ma per usare questo metodo, la lunghezza della frazione continua deve essere un numero dispari . Quindi [1;3] dovrebbe essere sostituito dalla frazione continua equivalente [1;2,1]. Quindi

i

= 1001 ₂ = 9.

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

Sequenza biatomica di Stern

Grafico a dispersione di

fusc(0...4096)

La sequenza biatomica di Stern è la sequenza intera

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ... (sequenza A002487 in OEIS ).

Usando la numerazione in base zero , l' $n-$ esimo valore nella sequenza è il valore $fusc(n)$ della funzione fusc , denominata in base all'aspetto offuscante della sequenza di valori e definita dalle relazioni di ricorrenza

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

con i casi base $fusc(0) = 0$ e $fusc(1) = 1$ .

L' $n-$ esimo numero razionale in un attraversamento in ampiezza dell'albero di Calkin-Wilf è il numero $fuc(n) / fuc(n + 1)$ . Pertanto, la sequenza biatomica forma sia la sequenza dei numeratori che la sequenza dei denominatori dei numeri nella sequenza di Calkin-Wilf.

La funzione $fusc(n + 1)$ è il numero di coefficienti binomiali dispari della forma $(n - r r)$ , $0 \leq 2 r < n$ , e conta anche il numero di modi di scrivere $n$ come somma dipotenze di duein cui ogni potenza ricorre al massimo due volte. Questo può essere visto dalla ricorrenza che definisce fusc: le espressioni come somma di potenze di due per un numero pari $2 n$ o non hanno 1 in esse (nel qual caso sono formate raddoppiando ogni termine in un'espressione per $n$ ) o due 1s (nel qual 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 $2 n + 1$ è formata raddoppiando una rappresentazione per $n$ e aggiungendo 1, ancora una volta corrispondendo alla ricorrenza. Ad 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 $fusc(6 + 1) = 3$ .

Relazione con l'albero di Stern–Brocot

L'albero Calkin-Wilf assomiglia all'albero 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 comporta l'inversione delle rappresentazioni delle frazioni continue di questi numeri. Tuttavia, in altri modi, hanno proprietà diverse: per 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 contenuti. Questa proprietà non è vera per l'albero di Calkin-Wilf.

Appunti

Riferimenti

Aigner, Martin ; Ziegler, Günter M. (2004), Prove da THE BOOK (3a ed.), Berlino; New York: Springer, pp. 94-97, ISBN 978-3-540-40460-6
Bates, Bruce; Bunder, Martin; Tognetti, Keith (2010), "Linking the Calkin-Wilf and Stern-Brocot tree" , European Journal of Combinatorics , 31 (7): 1637–1661, doi : 10.1016/j.ejc.2010.04.002 , MR 2673006
Berstel, Jean; de Luca, Aldo (1997), "Parole di Sturmian, parole di Lyndon e alberi", Informatica teorica , 178 (1–2): 171–203, doi : 10.1016/S0304-3975 (96)00101-6
Calkin, Neil; Wilf, Herbert (2000), "Raccontare i razionali" (PDF) , American Mathematical Monthly , Mathematical Association of America , 107 (4): 360-363, doi : 10.2307/2589182 , JSTOR 2589182.
Carlitz, L. (1964), "Un problema nelle partizioni relative ai numeri di Stirling ", Bulletin of the American Mathematical Society , 70 (2): 275–278, doi : 10.1090/S0002-9904-1964-11118-6 , MR 0157907.
Dijkstra, Edsger W. (1982), scritti selezionati sull'informatica: una prospettiva personale , Springer-Verlag , ISBN 0-387-90652-5. EWD 570: An Exercise for Dr.RMBurstall , pp. 215-216, e EWD 578: More about the function "fusc" (A sequel to EWD570) , pp. 230-232, ristampe di note originariamente scritte nel 1976.
Gibbons, Jeremy ; Lester, David; Bird, Richard (2006), "Perla funzionale: enumerare i razionali", Journal of Functional Programming , 16 (3): 281–291, doi : 10.1017/S0956796806005880.
Raney, George N. (1973), "Sulle frazioni continue e automi finiti", Mathematische Annalen , 206 (4): 265–283, doi : 10.1007/BF01355980 , hdl : 10338.dmlcz/ 128216 , S2CID 120933574
Stern, Moritz A. (1858), "Ueber eine zahlentheoretische Funktion" , Journal für die reine und angewandte Mathematik , 55 : 193-220.

Languages

In other projects