Culkin Tree - Wilf

Calkin -Wilf-trädet är ett orienterat binärt träd vars hörn innehåller positiva rationella fraktioner enligt följande regel:

trädets rot är en bråkdel ; ${\frac {1}{1}}$
vertexet med en bråkdel har två barn: (vänster) och (höger). ${\frac {m}{n))$ ${\frac {m}{m+n))$ ${\frac {m+n}{n))$

Trädet beskrevs av Neil Culkin och Herbert S. Wilf (2000 [1] ) i samband med problemet med explicit omräkning [2] av mängden rationella tal.

Egenskaper för Culkin-Wilph-trädet

Grundläggande egenskaper

Alla fraktioner som ligger vid trädets hörn är irreducerbara;
Varje irreducerbar rationell fraktion förekommer exakt en gång i trädet.

Culkin-Wilph-sekvensen

Det följer av ovanstående egenskaper att sekvensen av positiva rationella tal som erhålls som ett resultat av bredd - första traversering [3] av Calkin-Wilf-trädet (även kallad Culkin-Wilf-sekvensen ; se illustrationen),

{\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

definierar en en-till-en-överensstämmelse mellan mängden naturliga tal och mängden positiva rationella tal.

Denna sekvens kan ges av återfallsrelationen [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 ,

där och betecknar heltals- och bråkdelar av talet , respektive . $\lgolv x\rgolv$ $\{x\}$ $x$

I Culkin-Wilf-sekvensen är nämnaren för varje bråk lika med täljaren för nästa.

fusc-funktion

År 1976 definierade E. Dijkstra heltalsfunktionen fusc( n ) på mängden naturliga tal genom följande rekursiva relationer [5] :

\operatörsnamn {fusc} (1)=1

;

\operatörsnamn {fusc} (2n)=\operatörsnamn {fusc} (n)

;

\operatörsnamn {fusc} (2n+1)=\operatörsnamn {fusc} (n)+\operatörsnamn {fusc} (n+1)

Sekvensen av värden sammanfaller med sekvensen av täljare av bråk i Calkin-Wilf-sekvensen, det vill säga sekvensen $\operatörsnamn {fusc} (n),n=1,2,3,\dots$

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

Således (eftersom nämnaren för varje bråkdel i Culkin-Wilf-sekvensen är lika med täljaren för nästa), är den :e termen i Culkin-Wilf-sekvensen , och överensstämmelsen $n$ $\operatörsnamn {fusc} (n)/\operatörsnamn {fusc} (n+1)$

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

är en en-till-en-överensstämmelse mellan mängden naturliga tal och mängden positiva rationella tal.

Funktionen kan, förutom ovanstående återkommande relationer, definieras enligt följande. $\operatörsnamn {fusc}$

Värdet är lika med antalet hyperbinära representationer av ett tal , det vill säga representationer i form av en summa av icke-negativa potenser av två, där varje grad förekommer högst två gånger [6] . Till exempel representeras siffran 6 på tre sätt: $\operatörsnamn {fusc} (n+1),n\geqslant 0$ $n$ $2^k$

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

\operatörsnamn {fusc} (6+1)=3

Värdet är lika med antalet alla udda binomialkoefficienter i formen , där [7] . $\operatörsnamn {fusc} (n+1),n\geqslant 0$ ${\binom {nr}{r))$ $0\leqslant 2r<n$

Den ursprungliga artikeln av Calkin och Wilf nämner inte funktionen, men anser att en heltalsfunktion definierad för , lika med antalet hyperbinära representationer av , och bevisar att korrespondensen $\operatörsnamn {fusc}$ $b(n)$ $n=0,1,2,\dots$ $n$

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

är en en-till-en-överensstämmelse mellan mängden icke-negativa heltal och mängden rationella tal. Alltså för $n=0,1,2,\dots$

b(n)=\operatörsnamn {fusc} (n+1),

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

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

Keplerträd och Saltus Gerberti

Se även

Stern Tree - Broko

Anteckningar

↑ Se Calkin, Wilf (2000) i bibliografin.
↑ Det vill säga en explicit tilldelning av en en-till-en-överensstämmelse mellan mängden naturliga tal och mängden (positiva) rationella tal. Standardbevisen för räknebarheten av uppsättningen av rationella tal använder vanligtvis inte den specificerade korrespondensen explicit.
↑ I det här fallet motsvarar "bredd"-genomgången den sekventiella genomgången av varje nivå (med början från toppen) av Calkin-Wilf-trädet från vänster till höger (se den första illustrationen).
↑ Funnet av Moshe Newman; se Aigner och Ziegler i bibliografin, sid. 108.
↑ Dokument EWD 570: En övning för Dr. R. M. Burstall Arkiverad 15 augusti 2021 på Wayback Machine ; återgiven i Dijkstra (1982) (se bibliografi), s. 215-216.
↑ I det här fallet anses det att talet 0 har en unik ("tom") hyperbinär representation 0 = 0, därför . $\operatörsnamn {fusc} (0+1)=1$
↑ Se Carlitz, L. Ett problem i partitioner relaterade till Stirling-talen // Bulletin of the American Mathematical Society. - 1964. - Vol. 70, nr 2 . - S. 275-278. Den här artikeln definierar en funktion som visar sig vara relaterad till funktionen fusc av relationen . $\theta _{0}(n)$ $\theta _{0}(n)=\operatörsnamn {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. Bevis från boken. Det bästa beviset från Euklids tid till våra dagar (översatt från engelska) . - M . : Mir, 2006. - S. 105 -109. — 256 sid. — ISBN 5-03-003690-3 . ( OBS : i denna översättning är efternamnet Wilf transkriberat som "Wilf".)
Dijkstra, E. W. Selected Writings on Computing: A Personal Perspective . - Springer-Verlag, 1982. - ISBN 0-387-90652-5 . (Se EWD 570 och EWD 578 återgivna i denna bok.)
Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. - 1858. - T. 55 . - S. 193-220 .
Shchetnikov AI Algoritm för att utveckla alla numeriska relationer från likhetsrelationen och Platons idealtal // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .