Fibonacciho slovo - Fibonacci word - Wikipedia

Charakterizace a sekvence řezání s čárou svahu ${ displaystyle 1 / varphi}$ nebo ${ displaystyle varphi -1}$, s ${ displaystyle varphi}$ the Zlatý řez.

${ displaystyle S_ {10}}$

${ displaystyle S_ {17}}$

Fibonacciho křivky vyrobeno z 10. a 17. Fibonacciho slova^[1]

A Fibonacciho slovo je specifická posloupnost binární číslice (nebo symboly z libovolných dvou písmen abeceda ). Fibonacciho slovo je tvořeno opakováním zřetězení stejným způsobem jako Fibonacciho čísla vznikají opakovaným přidáváním.

Je to paradigmatický příklad a Sturmian slovo a konkrétně a morfické slovo.

Název „Fibonacciho slovo“ byl také používán k označení členů a formální jazyk L skládající se z řetězců nul a jednotek bez dvou opakovaných. Jakákoli předpona konkrétního Fibonacciho slova patří L, ale také mnoho dalších řetězců. L má Fibonacciho počet členů každé možné délky.

Definice

Nechat ${ displaystyle S_ {0}}$ být „0“ a ${ displaystyle S_ {1}}$ být „01“. Nyní ${ displaystyle S_ {n} = S_ {n-1} S_ {n-2}}$ (zřetězení předchozí a předchozí sekvence).

Nekonečné slovo Fibonacci je limit ${ displaystyle S _ { infty}}$, tj. (jedinečná) nekonečná sekvence, která obsahuje každou ${ displaystyle S_ {n}}$, pro konečné ${ displaystyle n}$, jako předpona.

Výčet položek z výše uvedené definice vytváří:

${ displaystyle S_ {0}}$    0

${ displaystyle S_ {1}}$    01

${ displaystyle S_ {2}}$    010

${ displaystyle S_ {3}}$    01001

${ displaystyle S_ {4}}$    01001010

${ displaystyle 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 jednotlivé číslice

Pak^th číslice slova je ${ displaystyle 2+ left lfloor {{n} , varphi} right rfloor - left lfloor { left ({n + 1} right) , varphi} right rfloor}$ kde ${ displaystyle varphi}$ je Zlatý řez a ${ Displaystyle left lfloor x right rfloor}$ je funkce podlahy (sekvence A003849 v OEIS ). V důsledku toho lze nekonečné slovo Fibonacciho charakterizovat řeznou posloupností linie sklonu ${ displaystyle 1 / phi}$ nebo ${ displaystyle phi -1}$. Viz obrázek výše.

Pravidla střídání

Další způsob, jak jít S_n na S_n + 1 je nahradit každý symbol 0 v S_n s dvojicí po sobě následujících symbolů 0, 1 palce S_n + 1, a nahradit každý symbol 1 in S_n s jediným symbolem 0 in S_n + 1.

Alternativně si lze představit přímé generování celého nekonečného Fibonacciho slova následujícím způsobem: začněte kurzorem směřujícím na jednu číslici 0. Potom v každém kroku, pokud kurzor ukazuje na 0, připojte 1, 0 na konec slova a pokud kurzor ukazuje na 1, připojí na konec slova 0. V obou případech dokončete krok přesunutím kurzoru o jednu pozici doprava.

Podobné nekonečné slovo, někdy nazývané králičí sekvence, je generován podobným nekonečným procesem s jiným pravidlem nahrazení: kdykoli kurzor ukazuje na 0, přidá 1, a kdykoli kurzor ukazuje na 1, připojí 0, 1. Výsledná sekvence začíná

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 sekvence se však liší od Fibonacciho slova pouze triviálně, a to tak, že na 1 sekundu vyměníte 0s a posunete pozice o jednu.

Uzavřený výraz pro takzvanou králičí sekvenci:

Pak^th číslice slova je ${ displaystyle left lfloor {{n} , varphi} right rfloor - left lfloor { left ({n-1} right) , varphi} right rfloor -1}$ kde ${ displaystyle varphi}$ je Zlatý řez a ${ Displaystyle left lfloor x right rfloor}$ je funkce podlahy.

Diskuse

Slovo souvisí se slavnou stejnojmennou posloupností ( Fibonacciho sekvence ) v tom smyslu, že přidání celých čísel do indukční definice je nahrazeno zřetězením řetězce. To způsobí délku S_n být F_n + 2, (n + 2) Fibonacciho číslo. Také počet 1 s v S_n je F_n a počet 0 s v S_n je F_n + 1.

Další vlastnosti

• Nekonečné Fibonacciho slovo není periodické a v konečném důsledku není periodické.
• Poslední dvě písmena Fibonacciho slova jsou střídavě „01“ a „10“.
• Potlačením posledních dvou písmen slova Fibonacci nebo předponou doplňku posledních dvou písmen vytvoříte palindrom. Příklad: 01${ displaystyle S_ {4}}$ = 0101001010 je palindrom. The palindromická hustota nekonečného Fibonacciho slova je tedy 1 / φ, kde φ je Zlatý řez: toto je největší možná hodnota pro neperiodická slova.^[2]
• V nekonečném Fibonacciho slově je poměr (počet písmen) / (počet nul) φ, stejně jako poměr nul k jednotkám.
• Nekonečné slovo Fibonacci je a vyvážená sekvence: Vezmi si dva faktory stejně dlouhé kdekoli ve slově Fibonacci. Rozdíl mezi nimi Hammingovy závaží (počet výskytů „1“) nikdy nepřekročí 1.^[3]
• Podřízená slova 11 a 000 nikdy nenastane.
• The funkce složitosti nekonečného slova Fibonacci je n+1: obsahuje n+1 odlišná podřízená slova délky n. Příklad: K dispozici jsou 4 různá dílčí slova délky 3: „001“, „010“, „100“ a „101“. Protože je také neperiodický, má „minimální složitost“, a tedy a Sturmian slovo,^[4] se sklonem ${ displaystyle 1 / phi ^ {2}}$. Nekonečné slovo Fibonacci je standardní slovo generované direktivní sekvence (1,1,1,....).
• Nekonečné Fibonacciho slovo se opakuje; to znamená, že každé podslovo se vyskytuje nekonečně často.
• Li ${ displaystyle u}$ je podslovem nekonečného Fibonacciho slova, tak je označen i jeho obrácení ${ displaystyle u ^ {R}}$.
• Li ${ displaystyle u}$ je podslovem nekonečného Fibonacciho slova, tedy nejmenší periody ${ displaystyle u}$ je Fibonacciho číslo.
• Zřetězení dvou po sobě jdoucích Fibonacciho slov je „téměř komutativní“. ${ displaystyle S_ {n + 1} = S_ {n} S_ {n-1}}$ a ${ displaystyle S_ {n-1} S_ {n}}$ se liší pouze svými posledními dvěma písmeny.
• Číslo 0.010010100 ..., jehož desetinná místa jsou sestavena z číslic nekonečného Fibonacciho slova, je transcendentální.
• Písmena "1" lze nalézt na pozicích daných postupnými hodnotami sekvence Upper Wythoff (sekvence A001950 v OEIS ): ${ displaystyle lfloor n phi ^ {2} rfloor}$
• Písmena "0" lze nalézt na pozicích daných postupnými hodnotami dolní Wythoffovy sekvence (sekvence A000201 v OEIS ): ${ displaystyle lfloor n phi rfloor}$
• Distribuce ${ displaystyle n = F_ {k}}$ body na jednotkové kružnici, umístěné postupně ve směru hodinových ručiček o zlatý úhel ${ displaystyle { frac {2 pi} { phi ^ {2}}}}$, generuje vzor dvou délek ${ displaystyle { frac {2 pi} { phi ^ {k-1}}}, { frac {2 pi} { phi ^ {k}}}}$ na jednotkovém kruhu. Ačkoli výše uvedený proces generování Fibonacciho slova přímo neodpovídá postupnému dělení kruhových segmentů, je tento vzor ${ displaystyle S_ {k-1}}$ začíná-li vzor v bodě nejblíže k prvnímu bodu ve směru hodinových ručiček, potom 0 odpovídá dlouhé vzdálenosti a 1 krátké vzdálenosti.
• Nekonečné slovo Fibonacci obsahuje opakování 3 po sobě jdoucích stejných dílčích slov, ale žádné ze 4. The kritický exponent protože nekonečné slovo Fibonacci je ${ displaystyle 2+ phi přibližně 3,618}$.^[5] Je to nejmenší index (nebo kritický exponent) ze všech Sturmianových slov.
• Nekonečné slovo Fibonacci je často citováno jako nejhorší případ pro algoritmy detekující opakování v řetězci.
• Nekonečné slovo Fibonacci je a morfické slovo, generované v {0,1} * endomorfismem 0 → 01, 1 → 0.^[6]
• The nth prvek Fibonacciho slova, ${ displaystyle s_ {n}}$, je 1, pokud Zeckendorfova reprezentace (součet konkrétní sady Fibonacciho čísel) z n zahrnuje 1 a 0, pokud neobsahuje 1.

Aplikace

Konstrukce založené na Fibonacci se v současné době používají k modelování fyzických systémů s neperiodickým řádem, jako je kvazikrystaly. K pěstování vrstev krystalů Fibonacci a ke studiu jejich vlastností rozptylu světla byly použity techniky růstu krystalů.^[7]

Viz také

• Matematika a umění
• Tribonacciho slovo

Poznámky

Reference

• Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatické sekvence: Teorie, Aplikace, Zobecnění, Cambridge University Press, ISBN  978-0-521-82332-6.
• Dharma-wardana, M. W. C .; MacDonald, A. H .; Lockwood, D. J .; Baribeau, J.-M .; Houghton, D. C. (1987), „Ramanův rozptyl ve Fibonacciho superlattices“, Dopisy o fyzické kontrole, 58: 1761–1765, doi:10.1103 / physrevlett.58.1761, PMID  10034529.
• Lothaire, M. (1997), Kombinatorika slovEncyklopedie matematiky a její aplikace 17 (2. vyd.), Cambridge University Press, ISBN  0-521-59924-5.
• Lothaire, M. (2011), Algebraická kombinatorika na slovechEncyklopedie matematiky a její aplikace 90, Cambridge University Press, ISBN  978-0-521-18071-9. Dotisk vázané knihy z roku 2002.
• de Luca, Aldo (1995), „Divizní vlastnost Fibonacciho slova“, Dopisy o zpracování informací, 54 (6): 307–312, doi:10.1016 / 0020-0190 (95) 00067-M.
• Mignosi, F .; Pirillo, G. (1992), „Opakování ve Fibonacciho nekonečném slově“, Informační théorique et aplikace, 26 (3): 199–204.

externí odkazy

• Podrobný a přístupný popis na stránkách Rona Knotta
• Weisstein, Eric W. „Rabbit Sequence“. MathWorld.
• Fibonacciho slovo (prvních 200 000 bitů) na Youtube