Cuvânt Fibonacci - Fibonacci word

Caracterizarea printr - o secvență de tăiere cu o linie de pantă sau cu raportul de aur .

{\ displaystyle 1 / \ varphi}

{\ displaystyle \ varphi -1}

{\ displaystyle \ varphi}

{\ displaystyle S_ {10}}

{\ displaystyle S_ {17}}

Curbele Fibonacci realizate din cuvintele Fibonacci 10 și 17

Un cuvânt Fibonacci este o secvență specifică de cifre binare (sau simboluri din orice alfabet din două litere ). Cuvântul Fibonacci este format prin concatenare repetată în același mod în care numerele Fibonacci sunt formate prin adunare repetată.

Este un exemplu paradigmatic al unui cuvânt sturmian și în mod specific, un cuvânt morfic .

Numele „cuvânt Fibonacci” a fost, de asemenea, folosit pentru a se referi la membrii unui limbaj formal L format din șiruri de zerouri și unii fără două repetate. Orice prefix al cuvântului specific Fibonacci aparține lui L , dar la fel fac multe alte șiruri. L are un număr de membri Fibonacci de fiecare lungime posibilă.

Definiție

Fie „0” și „01”. Acum (concatenarea secvenței anterioare și a celei anterioare). ${\ displaystyle S_ {0}}$ ${\ displaystyle S_ {1}}$ ${\ displaystyle S_ {n} = S_ {n-1} S_ {n-2}}$

Cuvântul infinit Fibonacci este limita , adică secvența infinită (unică) care conține fiecare , pentru finit , ca prefix. ${\ displaystyle S _ {\ infty}}$ ${\ displaystyle S_ {n}}$ ${\ displaystyle n}$

Enumerarea articolelor din definiția de mai sus produce:

${\ displaystyle S_ {0}}$ 0

${\ displaystyle S_ {1}}$ 01

${\ displaystyle S_ {2}}$ 010

${\ displaystyle S_ {3}}$ 01001

${\ displaystyle S_ {4}}$ 01001010

${\ displaystyle S_ {5}}$ 0100101001001

...

Primele câteva elemente ale cuvântului infinit Fibonacci sunt:

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, .. . (secvența A003849 în OEIS )

Expresie în formă închisă pentru cifre individuale

Cea de-a n- ^a cifră a cuvântului este unde este raportul auriu și este funcția etaj (secvența A003849 în OEIS ). În consecință, infinitul cuvânt Fibonacci poate fi caracterizat printr-o secvență de tăiere a unei linii de pantă sau . Vezi figura de mai sus. ${\ displaystyle 2+ \ left \ lfloor {{n} \, \ varphi} \ right \ rfloor - \ left \ lfloor {\ left ({n + 1} \ right) \, \ varphi} \ right \ rfloor}$ ${\ displaystyle \ varphi}$ ${\ displaystyle \ left \ lfloor x \ right \ rfloor}$ ${\ displaystyle 1 / \ phi}$ ${\ displaystyle \ phi -1}$

Reguli de substituire

Un alt mod de a trece de la S _n la S _{n + 1} este înlocuirea fiecărui simbol 0 în S _n cu perechea de simboluri consecutive 0, 1 în S _{n + 1} și înlocuirea fiecărui simbol 1 în S _n cu simbolul unic 0 în S _{n + 1} .

Alternativ, ne putem imagina generând direct întregul cuvânt Fibonacci infinit prin următorul proces: începeți cu un cursor care indică o singură cifră 0. Apoi, la fiecare pas, dacă cursorul indică un 0, atașați 1, 0 la sfârșit din cuvânt și, dacă cursorul indică un 1, adăugați 0 la sfârșitul cuvântului. În ambele cazuri, finalizați pasul deplasând cursorul cu o poziție spre dreapta.

Un cuvânt infinit similar, numit uneori secvența iepurelui , este generat de un proces infinit similar cu o regulă de înlocuire diferită: ori de câte ori cursorul indică un 0, adăugați 1 și ori de câte ori cursorul indică un 1, adăugați 0, 1 Secvența rezultată începe

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, ...

Cu toate acestea, această secvență diferă de cuvântul Fibonacci doar în mod trivial, schimbând 0 cu 1 și schimbând pozițiile cu una.

O expresie de formă închisă pentru așa-numita secvență de iepure:

Cea de-a n- ^a cifră a cuvântului este unde este raportul auriu și este funcția etajată . ${\ displaystyle \ left \ lfloor {{n} \, \ varphi} \ right \ rfloor - \ left \ lfloor {\ left ({n-1} \ right) \, \ varphi} \ right \ rfloor -1}$ ${\ displaystyle \ varphi}$ ${\ displaystyle \ left \ lfloor x \ right \ rfloor}$

Discuţie

Cuvântul este legat de celebra secvență cu același nume ( secvența Fibonacci ) în sensul că adăugarea numerelor întregi în definiția inductivă este înlocuită cu concatenarea șirurilor. Acest lucru face ca lungimea lui S _n să fie F _{n + 2} , ( n + 2) numărul Fibonacci. De asemenea, numărul de 1 în S _n este F _n, iar numărul de 0 în S _n este F _{n + 1} .

Alte proprietăți

Cuvântul infinit Fibonacci nu este periodic și nu în cele din urmă periodic.
Ultimele două litere ale unui cuvânt Fibonacci sunt alternativ „01” și „10”.
Suprimarea ultimelor două litere ale unui cuvânt Fibonacci sau prefixarea complementului ultimelor două litere creează un palindrom . Exemplu: 01 = 0101001010 este un palindrom. Densitatea palindrom a cuvântului Fibonacci infinit este , astfel , 1 / φ, unde φ este raportul de aur : aceasta este cea mai mare valoare posibilă pentru cuvintele aperiodice. ${\ displaystyle S_ {4}}$
În cuvântul infinit Fibonacci, raportul (numărul de litere) / (numărul de zerouri) este φ, la fel ca și raportul dintre zerouri și unii.
Cuvântul infinit Fibonacci este o secvență echilibrată : Luați doi factori de aceeași lungime oriunde în cuvântul Fibonacci. Diferența dintre greutățile lor Hamming (numărul de apariții al „1”) nu depășește niciodată 1.
Sub-cuvintele 11 și 000 nu apar niciodată.
Funcția de complexitate a cuvântului infinit Fibonacci este n +1: conține n +1 sub-cuvinte distincte de lungime n . Exemplu: Există 4 sub-cuvinte distincte cu lungimea 3: „001”, „010”, „100” și „101”. Fiind, de asemenea, non-periodic, are atunci o „complexitate minimă” și, prin urmare, un cuvânt sturmian , cu pantă . Cuvântul infinit Fibonacci este cuvântul standard generat de secvența directivă (1,1,1, ....). ${\ displaystyle 1 / \ phi ^ {2}}$
Cuvântul infinit Fibonacci este recurent; adică fiecare sub cuvânt apare infinit de des.
Dacă este un sub cuvânt al cuvântului infinit Fibonacci, atunci la fel este inversarea acestuia, notată . ${\ displaystyle u}$ ${\ displaystyle u ^ {R}}$
Dacă este un sub-cuvânt al cuvântului infinit Fibonacci, atunci cea mai mică perioadă a este un număr Fibonacci. ${\ displaystyle u}$ ${\ displaystyle u}$
Concatenarea a două cuvinte Fibonacci succesive este „aproape comutativă”. și diferă doar prin ultimele două litere. ${\ displaystyle S_ {n + 1} = S_ {n} S_ {n-1}}$ ${\ displaystyle S_ {n-1} S_ {n}}$
Numărul 0,010010100 ..., ale cărui zecimale sunt construite cu cifrele cuvântului infinit Fibonacci, este transcendental .
Literele „1” pot fi găsite la pozițiile date de valorile succesive ale secvenței Upper Wythoff (secvența A001950 în OEIS ): ${\ displaystyle \ lfloor n \ phi ^ {2} \ rfloor}$
Literele „0” pot fi găsite la pozițiile date de valorile succesive ale secvenței Wythoff inferioare (secvența A000201 în OEIS ): ${\ displaystyle \ lfloor n \ phi \ rfloor}$
Distribuția punctelor pe cercul unității, plasate consecutiv în sensul acelor de ceasornic de unghiul auriu , generează un model de două lungimi pe cercul unității. Deși procesul de generare de mai sus al cuvântului Fibonacci nu corespunde direct diviziunii succesive a segmentelor de cerc, acest model se întâmplă dacă modelul începe din punctul cel mai apropiat de primul punct în sensul acelor de ceasornic, după care 0 corespunde distanței lungi și 1 la distanța scurtă. ${\ displaystyle 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}}$
Cuvântul infinit Fibonacci conține repetări a 3 sub-cuvinte identice succesive, dar niciunul dintre 4. Exponentul critic pentru cuvântul infinit Fibonacci este . Este cel mai mic indice (sau exponent critic) dintre toate cuvintele sturmiene. ${\ displaystyle 2+ \ phi \ approx 3.618}$
Cuvântul infinit Fibonacci este adesea citat ca fiind cel mai rău caz pentru algoritmii care detectează repetări într-un șir.
Cuvântul infinit Fibonacci este un cuvânt morfic , generat în {0,1} * de endomorfismul 0 → 01, 1 → 0.
Al n- lea element al unui cuvânt Fibonacci ,, este 1 dacă reprezentarea Zeckendorf (suma unui set specific de numere Fibonacci) a lui n include 1 și 0 dacă nu include 1. ${\ displaystyle s_ {n}}$
Cifrele cuvântului Fibonacci pot fi obținute luând secvența numerelor fibbinare modulul 2.

Aplicații

Construcțiile bazate pe Fibonacci sunt utilizate în prezent pentru modelarea sistemelor fizice cu ordine aperiodică, cum ar fi cvasicristalele , iar în acest context cuvântul Fibonacci este numit și cvasicristalul Fibonacci . Tehnicile de creștere a cristalelor au fost folosite pentru a crește cristale stratificate Fibonacci și pentru a studia proprietățile lor de împrăștiere a luminii.

Vezi si

Note

Referințe

Adamczewski, Boris; Bugeaud, Yann (2010), „8. Transcendență și aproximare diofantină”, în Berthé, Valérie ; Rigo, Michael (eds.), Combinatorica, automatele și teoria numerelor , Enciclopedia matematicii și aplicațiile sale, 135 , Cambridge: Cambridge University Press , p. 443, ISBN 978-0-521-51597-9, Zbl 1271.11073.
Allouche, Jean-Paul; Shallit, Jeffrey (2003), Secvențe automate: teorie, aplicații, generalizări , Cambridge University Press , ISBN 978-0-521-82332-6.
Bombieri, E .; Taylor, JE (1986), "Care distribuții ale materiei difractă? O investigație inițială" (PDF) , Le Journal de Physique , 47 (C3): 19-28, doi : 10.1051 / jphyscol: 1986303 , MR 0866320.
Dharma-wardana, MWC; MacDonald, AH; Lockwood, DJ; Baribeau, J.-M .; Houghton, DC (1987), „Raman scattering in Fibonacci superlattices”, Physical Review Letters , 58 (17): 1761–1765, doi : 10.1103 / physrevlett.58.1761 , PMID 10034529.
Kimberling, Clark (2004), „Ordinea cuvintelor și seturilor de numere: cazul Fibonacci”, în Howard, Frederic T. (ed.), Applications of Fibonacci Numbers, Volumul 9: Proceedings of the Xth International Research Conference on Fibonacci Numbers and Cererile lor , Dordrecht: Kluwer Academic Publishers, pp. 137–144, doi : 10.1007 / 978-0-306-48517-6_14 , MR 2076798.
Lothaire, M. (1997), Combinatorics on Words , Encyclopedia of Mathematics and its Applications, 17 (ediția a doua), Cambridge University Press , ISBN 0-521-59924-5.
Lothaire, M. (2011), Algebraic Combinatorics on Words , Encyclopedia of Mathematics and its Applications, 90 , Cambridge University Press , ISBN 978-0-521-18071-9. Reimprimarea Hardback-ului din 2002.
de Luca, Aldo (1995), „O proprietate de diviziune a cuvântului Fibonacci”, Scrisori de procesare a informațiilor , 54 (6): 307–312, doi : 10.1016 / 0020-0190 (95) 00067-M.
Mignosi, F .; Pirillo, G. (1992), „Repetiții în cuvântul infinit Fibonacci” , Informatique théorique et application , 26 (3): 199–204, doi : 10.1051 / ita / 1992260301991.
Ramírez, José L .; Rubiano, Gustavo N .; De Castro, Rodrigo (2014), „A generalization of the Fibonacci word fractal and the Fibonacci snowflake”, Theoretical Computer Science , 528 : 40–56, arXiv : 1212.1368 , doi : 10.1016 / j.tcs.2014.02.003 , MR 3175078.

Languages

In other projects