Fibonacciho slovo

Fibonacciho slovo je nějaká sekvence binárních číslic (nebo symbolů z libovolné dvoupísmenné abecedy ). Fibonacciho slovo je tvořeno opakovaným zřetězením stejným způsobem, jakým se Fibonacciho čísla tvoří opakovaným sčítáním.

Slovo Fibonacci je učebnicovým příkladem slova Sturm .

Název „Fibonacciho slovo“ se také používá k označení členů formálního jazyka L , který obsahuje řetězce nul a jedniček bez sousedních. Jakákoli část určitého Fibonacciho slova patří do L , ale v jazyce existuje mnoho dalších řetězců. V L je počet řetězců každé možné délky Fibonacciho číslo.

Definice

Nechť se rovná "0" a rovná se "01". Nyní (zřetězení předchozího členu a členu před ním). $S_{0}$ $S_{1}$ ${\displaystyle S_{n}=S_{n-1}S_{n-2))$

Nekonečné Fibonacciho slovo je limit . ${\displaystyle S_{\infty ))$

Výpis členů posloupnosti z výše uvedené definice dává:

$S_{0}$ 0

$S_{1}$ 01

$S_{2}$ 010

$S_{3}$ 01001

$S_4$ 01001010

$S_5$ 0100101001001

…

Prvních několik prvků nekonečného Fibonacciho slova je:

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, … ( sekvence A003849 v OEIS )

Uzavřený výraz pro konkrétní číslice

Číslice s číslem n slova se rovná , kde je zlatý řez a je funkcí "podlaha" ("podlaha"). $2+\left\lpatro {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor$ $\varphi$ $\left\lpatro x\right\rfloor$

Pravidla střídání

Dalším způsobem, jak přejít od Sn k Sn + 1 , je nahradit každou 0 v Sn dvojicí 0 , 1 a nahradit každou 1 0.

Alternativně si lze představit generování celého nekonečného Fibonacciho slova následujícím postupem. Začneme znakem 0, umístíme na něj kurzor. V každém kroku, pokud kurzor ukazuje na 0, přidejte 1 a 0 na konec slova, a pokud kurzor ukazuje na 1, přidejte 0 na konec slova. V obou případech je krok dokončen posunutím o jednu pozici doprava.

Podobné nekonečné slovo, někdy nazývané zlatá struna nebo králičí sekvence , je vytvořeno podobným nekonečným procesem, ale pravidlo substituce je jiné - pokud kurzor ukazuje na 0, přidejte 1, a pokud ukazuje na 1, přidejte 0, 1. Výsledná sekvence začíná na

0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, …

Tato posloupnost se však od Fibonacciho slova liší triviálně – nuly jsou nahrazeny jedničkami a celá posloupnost je posunuta o jedničku.

Uzavřený výraz pro zlatý řetězec je:

Číslice s číslem n slova se rovná , kde je zlatý řez a je to funkce „podlaha“ . $\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1$ $\varphi$ $\left\lpatro x\right\rfloor$

Diskuse

Slovo souvisí se slavnou stejnojmennou posloupností ( Fibonacciho posloupnost ) v tom, že přidání celých čísel v induktivní definici je nahrazeno zřetězením řetězců. To má za následek, že délka Sn je F n + 2 , ( n + 2 ) Fibonacciho číslo. Také počet jedniček v Sn je Fn a počet nul v Sn je Fn + 1 .

Další vlastnosti

Nekonečné Fibonacciho slovo není periodické a není nakonec periodické [1] .
Poslední dvě číslice Fibonacciho slova jsou buď „01“ nebo „10“.
Odstraněním posledních dvou písmen Fibonacciho slova nebo přidáním posledních dvou písmen na začátek doplňku vznikne palindrom . Příklad: 01 =0101001010 je palindrom. Palindromická hustota nekonečného Fibonacciho slova je 1/φ, kde φ je zlatý řez . Toto je největší možná hodnota pro neperiodická slova [2] . $S_4$
V nekonečném Fibonacciho slově je poměr (počet číslic)/(počet nul) roven φ, stejně jako poměr počtu nul k počtu jedniček.
Nekonečné Fibonacciho slovo je vyvážená posloupnost . Vezměte dva podřetězce stejné délky kdekoli ve Fibonacciho slově. Rozdíl mezi jejich Hammingovými váhami (počet jednotek) nikdy nepřekročí 1 [3] .
Podslova 11 a 000 se nikdy nevyskytují.
Funkce složitosti nekonečného Fibonacciho slova je n + 1 — obsahuje n + 1 různých podslov o délce n . Příklad: Existují 4 různá podslova délky 3: "001", "010", "100" a "101". Být neperiodické sekvence, slovo má "minimální složitost", a proto je Sturm slovo [4] se sklonem. Nekonečné Fibonacciho slovo je standardní slovo tvořené direktivní posloupností (1,1,1,….). $1/\phi ^{2}$
Nekonečné Fibonacciho slovo se opakuje. To znamená, že jakékoli podslovo se vyskytuje nekonečně často.
Jestliže je podslovo nekonečného Fibonacciho slova, pak podslovo je jeho inverzní, značená . $u$ $u^{R}$
Jestliže je podslovo nekonečného Fibonacciho slova, pak nejmenší tečka je Fibonacciho číslo. $u$ $u$
Zřetězení dvou sekvencí Fibonacciho slov je „téměř komutativní“. a liší se pouze v posledních dvou písmenech. ${\displaystyle S_{n+1}=S_{n}S_{n-1))$ ${\displaystyle S_{n-1}S_{n))$
V důsledku toho lze nekonečné Fibonacciho číslo popsat posloupností úseků přímky se sklonem nebo . Viz obrázek výše. $\phi$ $\phi-1$
Číslo 0,010010100…, jehož desetinné číslice jsou číslice nekonečného Fibonacciho slova, je transcendentální .
Písmena "1" lze nalézt na pozicích daných po sobě jdoucími hodnotami horní Wythoffovy sekvence ( OEIS A001950): $\lfloor n\phi ^{2}\rfloor$
Písmena "0" lze nalézt na pozicích daných po sobě jdoucími hodnotami nižší Wythoffovy sekvence (OEIS A000201): $\lfloor n\phi \rfloor$
Rozložení bodů na jednotkové kružnici , umístěné postupně ve směru hodinových ručiček pod zlatým úhlem , tvoří vzor dvou délek na jednotkové kružnici. Ačkoli výše popsaný Fibonacciho proces tvorby slov přímo neodpovídá sekvenčnímu dělení segmentů kruhu, tento vzor je roven tomu, když začínáme od nejbližšího bodu ve směru hodinových ručiček, přičemž 0 odpovídá velké vzdálenosti a 1 odpovídá krátké vzdálenosti. $n=F_{k}$ ${\displaystyle {\frac {2\pi }{\phi ^{2))))$ ${\displaystyle {\frac {2\pi }{\phi ^{k-1))}, {\frac {2\pi }{\phi ^{k))))$ ${\displaystyle S_{k-1))$
Nekonečné Fibonacciho slovo může obsahovat 3 po sobě jdoucí stejná podslova, ale nikdy 4 taková podslova. Kritický index pro nekonečné Fibonacciho slovo je roven opakování [5] . Toto je nejmenší index (nebo kritický index) ze všech Sturmových slov. $2+\phi =3,618$
Nekonečné Fibonacciho slovo je často citováno jako nejhorší případ pro algoritmy detekce opakování řetězců
Nekonečné Fibonacciho slovo je morfické slovo vytvořené z {0,1}* endomorfismem 0 → 01, 1 → 0 [6] .

Aplikace

Fibonacciho slovní konstrukce se používají k modelování fyzikálních systémů s neperiodickým uspořádáním, jako jsou kvazikrystaly , a ke studiu vlastností rozptylu světla krystalů s Fibonacciho vrstvami [7] .

Viz také

Matematika a výtvarné umění
Slovo tribonacci

Poznámky

↑ Posloupnost se nazývá konečně periodická s parametry , pokud podmínka pro , kde a jsou celá čísla, , . Nejmenší takové číslo se nazývá perioda posloupnosti. Sekvence se nazývá -periodická if ( Lipnitsky a Chesalin 2008 , s. 27). $v=(v_{0},v_{1},\ldots )$ $(T,\tau )$ $v_{k+T}=v_{k}$ $k\geqslant \tau$ $T$ $\tau$ $T>0$ $\tau >0$ $T$ $T$ $\tau=0$
↑ Adamczewski, Bugeaud, 2010 , str. 443.
↑ Lothaire, 2011 , str. 47.
↑ de Luca (1995) .
↑ Allouche, Shallit, 2003 , str. 37.
↑ Lothaire, 2011 , str. jedenáct.
↑ Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987 .

Literatura

Jean-Paul Allouche, Jeffrey Shallit. Automatické sekvence: Teorie, Aplikace, Zobecnění. - Cambridge University Press , 2003. - ISBN 978-0-521-82332-6 .
Dharma-wardana MWC, MacDonald AH, Lockwood DJ, Baribeau J.-M., Houghton DC Ramanův rozptyl ve Fibonacciho supermřížkách // Physical Review Letters . - 1987. - T. 58 . - S. 1761-1765 . - doi : 10.1103/physrevlett.58.1761 .
Lothaire M. Kombinatorika na slovech. — 2. - Cambridge University Press , 1997. - V. 17. - (Encyklopedie matematiky a jejích aplikací). - ISBN 0-521-59924-5 .
Lothaire M. Algebraická kombinatorika na slovech. - Cambridge University Press , 2011. - V. 90. - (Encyklopedie matematiky a její aplikace). . Dotisk z roku 2002 v pevné vazbě.
Aldo de Luca. Vlastnost dělení Fibonacciho slova // Information Processing Letters . - 1995. - T. 54 , no. 6 . — S. 307–312 . - doi : 10.1016/0020-0190(95)00067-M .
Mignosi F., Pirillo G. Opakování ve Fibonacciho nekonečném slově // Informatique théorique et application. - 1992. - T. 26 , no. 3 . — S. 199–204 .
Boris Adamczewski, Yann Bugeaud. Kapitola 8. Transcendence a diofantická aproximace // Kombinatorika, automaty a teorie čísel / Valérie Berthé, Michael Rigo. - Cambridge: Cambridge University Press , 2010. - V. 135. - S. 443. - (Encyklopedie matematiky a její aplikace). - ISBN 978-0-521-51597-9 .
Lipnitsky V. A., Chesalin N. V. Lineární kódy a kódové sekvence: učebnicová metoda. Manuál pro studenty mech.mat. Fak. BGU . - Minsk: BGU, 2008.

Odkazy

Podrobný a dostupný popis na stránkách Rona Knotta
Weisstein, Eric W. Rabbit Sequence (anglicky) na webových stránkách Wolfram MathWorld .
video na YouTube _