Arborele Culkin - Wilf

Arborele Calkin-Wilf este un arbore binar orientat ale cărui vârfuri conțin fracții raționale pozitive conform următoarei reguli:

rădăcina arborelui este o fracție ; ${\frac {1}{1}}$
vârful cu o fracție are doi copii: (stânga) și (dreapta). ${\frac {m}{n)}$ ${\frac {m}{m+n)}$ ${\frac {m+n}{n})$

Arborele a fost descris de Neil Culkin și Herbert S. Wilf (2000 [1] ) în legătură cu problema recalculării explicite [2] a mulțimii numerelor raționale.

Proprietățile arborelui Culkin-Wilph

Proprietăți de bază

Toate fracțiile situate la vârfurile arborelui sunt ireductibile;
Orice fracție rațională ireductibilă apare exact o dată în arbore.

Secvența Culkin-Wilph

Din proprietățile de mai sus rezultă că succesiunea de numere raționale pozitive obținute ca urmare a lățimii - prima traversare [3] a arborelui Calkin-Wilf (numită și secvența Culkin-Wilf ; vezi ilustrația),

{\frac {1}{1)),{\frac {1}{2}),{\frac {2}{1)),{\frac {1}{3)),{\frac {3}{2)),{\frac {2}{3)),{\frac {3}{1)),{\frac {1}{4)),{\frac {4}{3} },{\frac {3}{5)),{\frac {5}{2)),{\frac {2}{5)),{\frac {5}{3)),{\frac { 3}{4}},\puncte

definește o corespondență unu-la-unu între mulțimea numerelor naturale și mulțimea numerelor raționale pozitive.

Această secvență poate fi dată de relația de recurență [4]

q_{1}=1;

q_{i+1}={\frac {1}{\lfloor q_{i}\rfloor +1-\{q_{i}\))}={\frac {1}{2\lfloor q_ {i}\rfloor -q_{i}+1}},\quad i=1,2,\dots ,

unde și notăm părțile întregi și , respectiv, fracționale ale numărului . $\lfloor x\rfloor$ $\{X\}$ $X$

În secvența Culkin-Wilf, numitorul fiecărei fracții este egal cu numărătorul următoarei.

funcția fusc

În 1976, E. Dijkstra a definit funcția întreg fusc( n ) pe mulțimea numerelor naturale prin următoarele relații recursive [5] :

\operatorname {fusc} (1)=1

;

\operatorname {fusc} (2n)=\operatorname {fusc} (n)

;

\operatorname {fusc} (2n+1)=\operatorname {fusc} (n)+\operatorname {fusc} (n+1)

Secvența valorilor coincide cu succesiunea numărătorilor fracțiilor din secvența Calkin-Wilf, adică secvența $\operatorname {fusc} (n), n=1,2,3,\dots$

1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, …

Astfel (deoarece numitorul fiecărei fracții din șirul Culkin-Wilf este egal cu numărătorul următoarei), al treilea termen al șirului Culkin-Wilf este , iar corespondența $n$ $\operatorname {fusc} (n)/\operatorname {fusc} (n+1)$

n\mapsto {\frac {\operatorname {fusc} (n)}{\operatorname {fusc} (n+1))),\quad n=1,2,3,\dots

este o corespondență unu-la-unu între mulțimea numerelor naturale și mulțimea numerelor raționale pozitive.

Funcția poate fi, pe lângă relațiile de recurență de mai sus, definită după cum urmează. $\operatorname {fusc}$

Valoarea este egală cu numărul de reprezentări hiperbinare ale unui număr , adică reprezentări sub forma unei sume de puteri nenegative a două, unde fiecare grad apare de cel mult două ori [6] . De exemplu, numărul 6 este reprezentat în trei moduri: $\operatorname {fusc} (n+1), n\geqslant 0$ $n$ $2^k$

6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, deci .

\operatorname {fusc} (6+1)=3

Valoarea este egală cu numărul tuturor coeficienților binomi impari de forma , unde [7] . $\operatorname {fusc} (n+1), n\geqslant 0$ ${\binom {nr}{r)}$ $0\leqslant 2r<n$

Lucrarea originală a lui Calkin și Wilf nu menționează funcția, dar ia în considerare o funcție întreagă definită pentru , egală cu numărul de reprezentări hiperbinare ale lui , și demonstrează că corespondența $\operatorname {fusc}$ $b(n)$ $n=0,1,2,\dots$ $n$

n\mapsto {\frac {b(n)}{b(n+1))),\quad n=0,1,2,\dots

este o corespondență unu-la-unu între mulțimea numerelor întregi nenegative și mulțimea numerelor raționale. Astfel, pentru $n=0,1,2,\dots$

b(n)=\operatorname {fusc} (n+1),

b(2n+1)=b(n),

b(2n+2)=b(n)+b(n+1).

Arborele Kepler și Saltus Gerberti

Vezi și

Stern Tree - Broko

Note

↑ Vezi Calkin, Wilf (2000) în bibliografie.
↑ Adică, o atribuire explicită a unei corespondențe unu-la-unu între mulțimea numerelor naturale și mulțimea numerelor raționale (pozitive) . Demonstrațiile standard ale numărabilității mulțimii de numere raționale nu folosesc de obicei corespondența specificată în mod explicit.
↑ În acest caz, traversarea „în lățime” corespunde traversării secvențiale a fiecărui nivel (începând din partea de sus) a arborelui Calkin-Wilf de la stânga la dreapta (vezi prima ilustrație).
↑ Găsit de Moshe Newman; vezi Aigner şi Ziegler în bibliografie, p. 108.
↑ Documentul EWD 570: Un exercițiu pentru Dr. R. M. Burstall Arhivat 15 august 2021 la Wayback Machine ; reprodus în Dijkstra (1982) (vezi bibliografie), pp. 215-216.
↑ În acest caz, se consideră că numărul 0 are o reprezentare hiperbinară unică („vide”) 0 = 0, deci . $\operatorname {fusc} (0+1)=1$
↑ Vezi Carlitz, L. A problem in partitions related to the Stirling numbers // Bulletin of the American Mathematical Society. - 1964. - Vol. 70, nr. 2 . - P. 275-278. Acest articol definește o funcție care se dovedește a fi legată de funcția fusc prin relația . $\theta _{0}(n)$ $\theta _{0}(n)=\operatorname {fusc} (n+1)$

Literatură

Calkin, N., Wilf HS Recounting the Rationals // The American Mathematical Monthly. - 2000. - Vol. 107, nr. 4 . - P. 360-363. ( JSTOR 2589182 )
Aigner M., Ziegler G. Dovezi din carte. Cele mai bune dovezi din vremea lui Euclid până în zilele noastre (tradus din engleză) . - M . : Mir, 2006. - S. 105 -109. — 256 p. — ISBN 5-03-003690-3 . ( NB : în această traducere, numele de familie Wilf este transcris ca „Wilf”.)
Dijkstra, E. W. Selectate Writings on Computing: A Personal Perspective . - Springer-Verlag, 1982. - ISBN 0-387-90652-5 . (Vezi EWD 570 și EWD 578 reproduse în această carte.)
Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. - 1858. - T. 55 . - S. 193-220 .
Shchetnikov AI Algoritm pentru desfășurarea tuturor relațiilor numerice din relația de egalitate și numerele ideale ale lui Platon // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .