Culkin Tree - Wilf

Calkin -Wilf-puu on suuntautunut binääripuu , jonka kärjet sisältävät positiivisia rationaalisia murtolukuja seuraavan säännön mukaisesti:

puun juuri on murto-osa ; ${\frac {1}{1))$
kärjessä, jossa on murto, on kaksi lasta: (vasen) ja (oikea). ${\frac {m}{n))$ ${\frac {m}{m+n))$ ${\frac {m+n}{n))$

Puun kuvasivat Neil Culkin ja Herbert S. Wilf (2000 [1] ) rationaalisten lukujen joukon eksplisiittisen uudelleenlaskennan [2] ongelman yhteydessä .

Culkin-Wilph-puun ominaisuudet

Perusominaisuudet

Kaikki puun huipuissa sijaitsevat jakeet ovat redusoitumattomia;
Mikä tahansa redusoitumaton rationaalinen murtoluku esiintyy puussa täsmälleen kerran.

Culkin-Wilph-sekvenssi

Yllä olevista ominaisuuksista seuraa , että Calkin-Wilf-puun leveys - ensimmäisen läpikäynnin [3] tuloksena saatu positiivisten rationaalilukujen sarja (kutsutaan myös Culkin-Wilf-sekvenssiksi ; katso kuva),

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

määrittää yksi-yhteen vastaavuuden luonnollisten lukujen joukon ja positiivisten rationaalilukujen joukon välillä.

Tämä sekvenssi voidaan antaa toistuvuusrelaatiolla [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 ,

jossa ja merkitsevät luvun kokonaislukua ja murto-osaa vastaavasti . $\lfloor x\rfloor$ $\{x\}$ $x$

Culkin-Wilf-sekvenssissä kunkin murtoluvun nimittäjä on yhtä suuri kuin seuraavan osoittaja .

fusc-funktio

Vuonna 1976 E. Dijkstra määritteli kokonaislukufunktion fusc( n ) luonnollisten lukujen joukolle seuraavilla rekursiivisilla suhteilla [5] :

\operaattorin nimi {fusc} (1)=1

;

\operaattorin nimi {fusc} (2n)=\operaattorin nimi {fusc} (n)

;

\operaattorin nimi {fusc} (2n+1)=\operaattorin nimi {fusc} (n)+\operaattorin nimi {fusc} (n+1)

Arvosarja on sama kuin Calkin -Wilf-sekvenssin murto-osien osoittajien sekvenssi, eli sekvenssi $\operaattorin nimi {fusc} (n),n=1,2,3,\pisteet$

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

Siten (koska Culkin-Wilf-sekvenssin jokaisen murtoluvun nimittäjä on yhtä suuri kuin seuraavan osoittaja), Culkin-Wilf-sekvenssin termi on , ja vastaavuus $n$ $\operaattorin nimi {fusc} (n)/\operaattorin nimi {fusc} (n+1)$

n\mapsto {\frac {\operaattorin nimi {fusc} (n)}{\operaattorin nimi {fusc} (n+1))),\quad n=1,2,3,\pisteet

on yksi yhteen vastaavuus luonnollisten lukujen joukon ja positiivisten rationaalilukujen joukon välillä.

Funktio voidaan edellä mainittujen toistuvuussuhteiden lisäksi määritellä seuraavasti. $\operaattorin nimi {fusc}$

Arvo on yhtä suuri kuin luvun hyperbinääriesitysten lukumäärä , toisin sanoen esitykset kahden ei-negatiivisten potenssien summan muodossa, jossa kukin aste esiintyy enintään kaksi kertaa [6] . Esimerkiksi numero 6 esitetään kolmella tavalla: $\operaattorin nimi {fusc} (n+1),n\geqslant 0$ $n$ $2^k$

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

\operaattorin nimi {fusc} (6+1)=3

Arvo on yhtä suuri kuin muodon kaikkien parittomien binomikertoimien lukumäärä , jossa [7] . $\operaattorin nimi {fusc} (n+1),n\geqslant 0$ ${\binom {nr}{r))$ $0\leqslant 2r<n$

Calkinin ja Wilfin alkuperäisessä artikkelissa ei mainita funktiota, mutta siinä tarkastellaan funktiolle määritettyä kokonaislukufunktiota , joka on yhtä suuri kuin funktion hyperbinääriesitysten lukumäärä, ja todistetaan , että vastaavuus $\operaattorin nimi {fusc}$ $b(n)$ ${\näyttötyyli n=0,1,2,\pisteet }$ $n$

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

on yksi yhteen vastaavuus ei-negatiivisten kokonaislukujen ja rationaalisten lukujen joukon välillä. Siten, varten ${\näyttötyyli n=0,1,2,\pisteet }$

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

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

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

Kepler-puu ja Saltus Gerberti

Katso myös

Stern Tree - Broko

Muistiinpanot

↑ Katso Calkin, Wilf (2000) bibliografiassa.
↑ Toisin sanoen luonnollisten lukujen joukon ja (positiivisten) rationaalilukujen joukon välisen yksi-yhteen vastaavuuden eksplisiittinen määritys . Rationaalilukujoukon laskettavuuden standarditodisteet eivät yleensä käytä määritettyä vastaavuutta eksplisiittisesti.
↑ Tässä tapauksessa "leveys"-läpikulku vastaa Calkin-Wilf-puun jokaisen tason (ylhäältä alkaen) peräkkäistä läpikulkua vasemmalta oikealle (katso ensimmäinen kuva).
↑ Löytäjä Moshe Newman; katso Aigner ja Ziegler bibliografiassa, s. 108.
↑ Asiakirja EWD 570: Harjoitus Dr. R. M. Burstall Arkistoitu 15. elokuuta 2021 Wayback Machinessa ; toistettu Dijkstrassa (1982) (katso bibliografia), s. 215-216.
↑ Tässä tapauksessa katsotaan, että luvulla 0 on ainutlaatuinen ("tyhjä") hyperbinääriesitys 0 = 0, joten . $\operaattorin nimi {fusc} (0+1)=1$
↑ Katso Carlitz, L. Stirling-lukuihin liittyvä ongelma osioissa // Bulletin of the American Mathematical Society. - 1964. - Voi. 70, nro 2 . - s. 275-278. Tässä artikkelissa määritellään funktio , joka osoittaa liittyvän funktioon fusc relaatiolla . $\theta _{0}(n)$ $\theta _{0}(n)=\operaattorinimi {fusc} (n+1)$

Kirjallisuus

Calkin, N., Wilf HS Recounting the Rationals // The American Mathematical Monthly. - 2000. - Voi. 107, nro 4 . - s. 360-363. ( JSTOR 2589182 )
Aigner M., Ziegler G. Todisteita kirjasta. Paras todiste Eukleideen ajasta nykypäivään (käännetty englannista) . - M . : Mir, 2006. - S. 105 -109. — 256 s. — ISBN 5-03-003690-3 . ( HUOM : tässä käännöksessä sukunimi Wilf on transkriptoitu "Wilf".)
Dijkstra, E. W. Selected Writings on Computing: A Personal Perspective . - Springer-Verlag, 1982. - ISBN 0-387-90652-5 . (Katsotässä kirjassa toistetut EWD 570 ja EWD 578. )
Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. - 1858. - T. 55 . - S. 193-220 .
Shchetnikov AI Algoritmi kaikkien numeeristen suhteiden avaamiseksi tasa-arvosuhteesta ja Platonin ideaaliluvuista // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .