Culkin Tree – Wilf

A Calkin-Wilf fa egy orientált bináris fa, amelynek csúcsai pozitív racionális törteket tartalmaznak a következő szabály szerint:

a fa gyökere töredék ; ${\frac {1}{1))$
a törttel rendelkező csúcsnak két gyermeke van: (bal) és (jobb). ${\frac {m}{n))$ ${\frac {m}{m+n))$ ${\frac {m+n}{n))$

A fát Neil Culkin és Herbert S. Wilf (2000 [1] ) írta le a racionális számok halmazának explicit újraszámításának [2] problémájával kapcsolatban.

A Culkin-Wilph fa tulajdonságai

Alaptulajdonságok

A fa csúcsaiban található összes tört irreducibilis;
Bármely irreducibilis racionális tört pontosan egyszer fordul elő a fában.

A Culkin-Wilph sorozat

A fenti tulajdonságokból következik, hogy a Calkin-Wilf fa szélessége - első bejárása [3] eredményeként kapott pozitív racionális számok sorozata ( Culkin-Wilf sorozatnak is nevezik ; lásd az ábrát),

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

egy az egyhez megfelelést határozza meg a természetes számok halmaza és a pozitív racionális számok halmaza között.

Ezt a sorozatot az ismétlődési reláció adja meg [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,\pontok ,

ahol és jelöli a szám egész , illetve tört részét . $\lfloor x\rfloor$ $\{x\}$ $x$

A Culkin-Wilf sorozatban minden tört nevezője egyenlő a következő számlálójával .

fusc függvény

1976- ban E. Dijkstra definiálta a fusc( n ) egész függvényt a természetes számok halmazán a következő rekurzív relációkkal [5] :

\operatorname {fusc} (1)=1

;

\operátornév {fusc} (2n)=\operátornév {fusc} (n)

;

\operátornév {fusc} (2n+1)=\operátornév {fusc} (n)+\operátornév {fusc} (n+1)

Az értéksor egybeesik a Calkin-Wilf sorozatban lévő törtek számlálóinak sorrendjével, azaz a sorozattal ${\megjelenítési stílus \operátornév {fusc} (n),n=1,2,3,\pontok}$

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

Így (mivel a Culkin-Wilf szekvencia minden törtjének nevezője egyenlő a következő számlálójával), a Culkin-Wilf szekvencia harmadik tagja , és a megfelelés $n$ $\operátornév {fusc} (n)/\operátornév {fusc} (n+1)$

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

a természetes számok halmaza és a pozitív racionális számok halmaza közötti egy-egy megfeleltetés.

A függvény a fenti ismétlődési viszonyok mellett a következőképpen definiálható. $\operátornév {fusc}$

Az érték megegyezik egy szám hiperbináris reprezentációinak számával , azaz a kettő nemnegatív hatványainak összege formájában megjelenő reprezentációk számával, ahol minden fokozat legfeljebb kétszer fordul elő [6] . Például a 6-os szám háromféleképpen ábrázolható: $\operatorname {fusc} (n+1),n\geqslant 0$ $n$ $2^k$

6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1, tehát .

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

Az érték megegyezik az alak összes páratlan binomiális együtthatójának számával , ahol [ 7 ] . $\operatorname {fusc} (n+1),n\geqslant 0$ ${\binom {nr}{r))$ $0\leqslant 2r<n$

Calkin és Wilf eredeti írása nem említi a függvényt, de figyelembe veszi a függvényhez definiált egész függvényt , amely megegyezik a hiperbináris reprezentációinak számával , és bizonyítja, hogy a megfelelés $\operátornév {fusc}$ $b(n)$ $n=0,1,2,\pontok$ $n$

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

a nemnegatív egész számok halmaza és a racionális számok halmaza közötti egy-egy megfeleltetés . Így a $n=0,1,2,\pontok$

b(n)=\operátornév {fusc} (n+1),

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

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

Kepler fa és Saltus Gerberti

Lásd még

Stern Tree - Broko

Jegyzetek

↑ Lásd Calkin, Wilf (2000) az irodalomjegyzékben.
↑ Vagyis a természetes számok halmaza és a (pozitív) racionális számok halmaza közötti egy-egy megfeleltetés explicit hozzárendelése . A racionális számok halmazának megszámlálhatóságának standard bizonyításai általában nem használják kifejezetten a megadott megfelelést.
↑ Ebben az esetben a "szélesség" bejárás megfelel a Calkin-Wilf fa minden szintjének szekvenciális bejárásának (felülről kezdve) balról jobbra (lásd az első ábrát).
↑ Moshe Newman találta; lásd Aigner és Ziegler a bibliográfiában, p. 108.
↑ EWD 570 dokumentum : Egy gyakorlat Dr. R. M. Burstall archiválva : 2021. augusztus 15. a Wayback Machine -nél ; reprodukálva: Dijkstra (1982) (lásd a bibliográfiát), pp. 215-216.
↑ Ebben az esetben azt tekintjük, hogy a 0 számnak egyedi ("üres") hiperbináris reprezentációja van 0 = 0, ezért . $\operatorname {fusc} (0+1)=1$
↑ Lásd Carlitz, L. A Stirling-számokkal kapcsolatos partíciók problémája // Bulletin of the American Mathematical Society. - 1964. - 1. évf. 70, 2. sz . - 275-278. Ez a cikk egy olyan függvényt határoz meg, amelyről kiderül, hogy a reláció kapcsolatban áll a fusc függvénnyel . $\theta _{0}(n)$ $\theta _{0}(n)=\operátornév {fusc} (n+1)$

Irodalom

Calkin, N., Wilf HS Recounting the Rationals // The American Mathematical Monthly. - 2000. - Vol. 107, 4. sz . - P. 360-363. ( JSTOR 2589182 )
Aigner M., Ziegler G. Bizonyítékok a könyvből. A legjobb bizonyíték Eukleidész korától napjainkig (angolból fordítva) . - M . : Mir, 2006. - S. 105 -109. — 256 p. — ISBN 5-03-003690-3 . ( Megjegyzés : ebben a fordításban a Wilf vezetéknév "Wilf"-ként van átírva .)
Dijkstra, E. W. Selected Writings on Computing: A Personal Perspective . - Springer-Verlag, 1982. - ISBN 0-387-90652-5 . (Lásd az EWD 570 és EWD 578 , amely ebben a könyvben szerepel.)
Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. - 1858. - T. 55 . - S. 193-220 .
Shchetnikov AI Algoritmus minden numerikus reláció kibontására az egyenlőségi relációból és Platón ideális számaiból // ΣΧΟΛΗ . - 2008. - T. 2 . - S. 55-74 . — ISSN 1995-4328 .