Culkin Tree - Wilf

Calkin -Wilf træet er et orienteret binært træ, hvis toppunkter indeholder positive rationelle fraktioner i henhold til følgende regel:

træets rod er en brøkdel ; ${\frac {1}{1}}$
toppunktet med en brøk har to børn: (venstre) og (højre). ${\frac {m}{n))$ ${\frac {m}{m+n))$ ${\frac {m+n}{n))$

Træet blev beskrevet af Neil Culkin og Herbert S. Wilf (2000 [1] ) i forbindelse med problemet med eksplicit genberegning [2] af sættet af rationelle tal.

Egenskaber for Culkin-Wilph træet

Grundlæggende egenskaber

Alle fraktioner, der er placeret i træets spidser, er irreducerbare;
Enhver irreducerbar rationel fraktion forekommer nøjagtigt én gang i træet.

Culkin-Wilph-sekvensen

Det følger af ovenstående egenskaber, at sekvensen af positive rationelle tal opnået som et resultat af bredden - første traversering [3] af Calkin-Wilf-træet (også kaldet Culkin-Wilf-sekvensen ; se illustration),

{\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}},\dots

definerer en en-til-en overensstemmelse mellem mængden af naturlige tal og mængden af positive rationelle tal.

Denne sekvens kan gives af gentagelsesrelationen [4]

q_{1}=1;

q_{i+1}={\frac {1}{\lgulv q_{i}\rgulv +1-\{q_{i}\))}={\frac {1}{2\lgulv q_ {i}\rgulv -q_{i}+1}},\quad i=1,2,\dots ,

hvor og betegner henholdsvis heltals- og brøkdelen af tallet . $\lgulv x\rgulv$ $\{x\}$ $x$

I Culkin-Wilf-sekvensen er nævneren for hver brøk lig med tælleren for den næste.

fusc funktion

I 1976 definerede E. Dijkstra heltalsfunktionen fusc( n ) på mængden af naturlige tal ved følgende rekursive relationer [5] :

\operatørnavn {fusc} (1)=1

;

\operatørnavn {fusc} (2n)=\operatørnavn {fusc} (n)

;

\operatørnavn {fusc} (2n+1)=\operatørnavn {fusc} (n)+\operatørnavn {fusc} (n+1)

Rækkefølgen af værdier falder sammen med sekvensen af tællere af brøker i Calkin-Wilf-sekvensen, det vil sige sekvensen $\operatørnavn {fusc} (n),n=1,2,3,\dots$

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

Således (da nævneren for hver brøk i Culkin-Wilf-sekvensen er lig med tælleren for den næste), er det th led i Culkin-Wilf-sekvensen , og korrespondancen $n$ $\operatørnavn {fusc} (n)/\operatørnavn {fusc} (n+1)$

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

er en en-til-en overensstemmelse mellem mængden af naturlige tal og mængden af positive rationelle tal.

Funktionen kan, udover ovenstående gentagelsesrelationer, defineres som følger. $\operatørnavn {fusc}$

Værdien er lig med antallet af hyperbinære repræsentationer af et tal , det vil sige repræsentationer i form af en sum af ikke-negative potenser af to, hvor hver grad ikke forekommer mere end to gange [6] . For eksempel er tallet 6 repræsenteret på tre måder: $\operatornavn {fusc} (n+1),n\geqslant 0$ $n$ $2^k$

6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, så .

\operatørnavn {fusc} (6+1)=3

Værdien er lig med antallet af alle ulige binomiale koefficienter på formen , hvor [7] . $\operatornavn {fusc} (n+1),n\geqslant 0$ ${\binom {nr}{r))$ $0\leqslant 2r<n$

Det originale papir af Calkin og Wilf nævner ikke funktionen, men betragter en heltalsfunktion defineret for , lig med antallet af hyperbinære repræsentationer af , og beviser, at korrespondancen $\operatørnavn {fusc}$ $b(n)$ $n=0,1,2,\dots$ $n$

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

er en en-til-en overensstemmelse mellem mængden af ikke-negative heltal og mængden af rationelle tal. Således for $n=0,1,2,\dots$

b(n)=\operatørnavn {fusc} (n+1),

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

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

Kepler træ og Saltus Gerberti

Se også

Stern Tree - Broko

Noter

↑ Se Calkin, Wilf (2000) i bibliografien.
↑ Det vil sige en eksplicit tildeling af en en-til-en overensstemmelse mellem mængden af naturlige tal og mængden af (positive) rationelle tal. Standardbeviserne for tælleligheden af sættet af rationelle tal bruger normalt ikke den specificerede korrespondance eksplicit.
↑ I dette tilfælde svarer "bredde"-gennemgangen til den sekventielle gennemkøring af hvert niveau (startende fra toppen) af Calkin-Wilf-træet fra venstre mod højre (se den første illustration).
↑ Fundet af Moshe Newman; se Aigner og Ziegler i bibliografien, s. 108.
↑ Dokument EWD 570: En øvelse for Dr. R. M. Burstall Arkiveret 15. august 2021 på Wayback Machine ; gengivet i Dijkstra (1982) (se bibliografi), s. 215-216.
↑ I dette tilfælde anses det for, at tallet 0 har en unik ("tom") hyperbinær repræsentation 0 = 0, derfor . $\operatørnavn {fusc} (0+1)=1$
↑ Se Carlitz, L. Et problem i partitioner relateret til Stirling-tallene // Bulletin of the American Mathematical Society. - 1964. - Bd. 70, nr. 2 . - S. 275-278. Denne artikel definerer en funktion , der viser sig at være relateret til funktionen fusc af relationen . $\theta _{0}(n)$ $\theta _{0}(n)=\operatørnavn {fusc} (n+1)$

Litteratur

Calkin, N., Wilf HS Recounting the Rationals // The American Mathematical Monthly. - 2000. - Vol. 107, nr. 4 . - S. 360-363. ( JSTOR 2589182 )
Aigner M., Ziegler G. Beviser fra bogen. Det bedste bevis fra Euklids tid til i dag (oversat fra engelsk) . - M . : Mir, 2006. - S. 105 -109. — 256 s. — ISBN 5-03-003690-3 . ( NB : i denne oversættelse er efternavnet Wilf transskriberet som "Wilf".)
Dijkstra, E. W. Udvalgte skrifter om databehandling: et personligt perspektiv . - Springer-Verlag, 1982. - ISBN 0-387-90652-5 . (Se EWD 570 og EWD 578 gengivet i denne bog.)
Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. - 1858. - T. 55 . - S. 193-220 .
Shchetnikov AI Algoritme til at udfolde alle numeriske relationer fra lighedsrelationen og Platons ideelle tal // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .