Fibonacci-ord

Fibonacci-ordet är en sekvens av binära siffror (eller symboler från valfritt alfabet med två bokstäver ) . Fibonacci-ordet bildas av upprepad sammanlänkning på samma sätt som Fibonacci-tal bildas av upprepade tillägg.

Ordet Fibonacci är ett läroboksexempel på ordet Sturm .

Namnet "Fibonacci-ord" används också för att beteckna medlemmar av det formella språket L , som innehåller strängar med nollor och ettor utan intilliggande. Vilken del av ett visst Fibonacci-ord som helst tillhör L , men det finns många andra strängar i språket. I L är antalet strängar av varje möjlig längd ett Fibonacci-tal.

Definition

Låt det vara lika med "0" och lika med "01". Nu (sammankoppling av föregående medlem och medlemmen före den). $S_{0}$ $S_{1}$ ${\displaystyle S_{n}=S_{n-1}S_{n-2))$

Det oändliga Fibonacci-ordet är gränsen . ${\displaystyle S_{\infty ))$

Att lista medlemmarna i sekvensen från definitionen ovan ger:

$S_{0}$ 0

$S_{1}$ 01

$S_{2}$ 010

$S_{3}$ 01001

$S_4$ 01001010

$S_5$ 0100101001001

…

De första elementen i det oändliga Fibonacci-ordet är:

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, … ( sekvens A003849 i OEIS )

Uttryck i slutet format för specifika siffror

Siffran med numret n i ordet är lika med , där är det gyllene snittet , och är funktionen "golv" ("golv"). $2+\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor$ $\varphi$ $\left\lfloor x\right\rfloor$

Ersättningsregler

Ett annat sätt att gå från S n till S n + 1 är att ersätta varje 0 i S n med ett par 0, 1 och ersätta varje 1 med en 0.

Alternativt kan man tänka sig att generera hela det oändliga Fibonacci-ordet med följande process. Vi börjar med tecknet 0, vi placerar markören på det. Vid varje steg, om markören pekar på 0, lägg till 1 och 0 i slutet av ordet, och om markören pekar på 1, lägg till 0 i slutet av ordet. I båda fallen avslutas steget genom att flytta en position åt höger.

Ett liknande oändligt ord, ibland kallat en gyllene sträng eller en kaninsekvens , bildas av en liknande oändlig process, men substitutionsregeln är annorlunda - om markören pekar på 0, lägg till 1, och om den pekar på 1, lägg till 0, 1. Den resulterande sekvensen börjar med

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

Denna sekvens skiljer sig dock trivialt från Fibonacci-ordet - nollor ersätts med ettor och hela sekvensen skiftas med en.

Det slutna formuttrycket för den gyllene strängen är:

Siffran med numret n i ordet är lika med , där är det gyllene snittet , och är funktionen "golv" . $\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1$ $\varphi$ $\left\lfloor x\right\rfloor$

Diskussion

Ordet är relaterat till den berömda sekvensen med samma namn ( Fibonacci-sekvensen ) genom att tillägget av heltal i den induktiva definitionen ersätts med strängsammansättning. Detta resulterar i att längden på S n är F n + 2 , ( n + 2):e Fibonacci-talet. Dessutom är antalet ettor i S n Fn och antalet nollor i S n är Fn + 1 .

Andra egenskaper

Det oändliga Fibonacci-ordet är inte periodiskt och är inte slutligen periodiskt [1] .
De två sista siffrorna i Fibonacci-ordet är antingen "01" eller "10".
Att ta bort de två sista bokstäverna i Fibonacci-ordet eller lägga till de två sista bokstäverna i början av komplementet skapar en palindrom . Exempel: 01 =0101001010 är en palindrom. Den palindromiska tätheten för ett oändligt Fibonacci-ord är 1/φ, där φ är det gyllene snittet . Detta är det största möjliga värdet för icke-periodiska ord [2] . $S_4$
I ett oändligt Fibonacci-ord är förhållandet (antal siffror)/(antal nollor) lika med φ, liksom förhållandet mellan antalet nollor och antalet ettor.
Det oändliga Fibonacci-ordet är en balanserad sekvens . Ta två delsträngar av samma längd var som helst i Fibonacci-ordet. Skillnaden mellan deras Hamming-vikter (antal enheter) överstiger aldrig 1 [3] .
Underord 11 och 000 förekommer aldrig.
Komplexitetsfunktionen ett oändligt Fibonacci-ord är n + 1 — det innehåller n + 1 distinkta underord med längden n . Exempel: Det finns 4 olika underord med längd 3: "001", "010", "100" och "101". Eftersom ordet är en icke-periodisk sekvens, har ordet "minimikomplexitet", och är därför ett Sturm-ord [4] med lutning. Ett oändligt Fibonacci-ord är ett standardord som bildas av direktivsekvensen (1,1,1,...). $1/\phi ^{2}$
Det oändliga Fibonacci-ordet är återkommande. Det vill säga, vilket underord som helst förekommer oändligt ofta.
Om är ett underord till ett oändligt Fibonacci-ord, då är underordet dess invers, betecknat med . $u$ $u^{R}$
Om är ett underord till ett oändligt Fibonacci-ord, då är den minsta perioden ett Fibonacci-tal. $u$ $u$
Sammansättningen av två sekvenser av Fibonacci-ord är "nästan kommutativ". och skiljer sig endast i de två sista bokstäverna. ${\displaystyle S_{n+1}=S_{n}S_{n-1))$ ${\displaystyle S_{n-1}S_{n))$
Som en konsekvens kan ett oändligt Fibonacci-tal beskrivas av en sekvens av sektioner av en rät linje med en lutning eller . Se bilden ovan. $\phi$ $\phi -1$
Talet 0,010010100…, vars decimalsiffror är siffrorna i det oändliga Fibonacci-ordet, är transcendentalt .
Bokstäverna "1" kan hittas i positioner som ges av successiva värden i den övre Wythoff-sekvensen ( OEIS A001950): $\lfloor n\phi ^{2}\rfloor$
Bokstäverna "0" kan hittas i positioner som ges av successiva värden i den nedre Wythoff-sekvensen (OEIS A000201): $\lfloor n\phi \rfloor$
En fördelning av punkter på enhetscirkeln , placerad i tur och ordning medurs i den gyllene vinkeln , bildar ett mönster av två längder på enhetscirkeln. Även om Fibonacci-ordbildningsprocessen som beskrivs ovan inte direkt motsvarar den sekventiella uppdelningen av cirkelsegment, är detta mönster lika med när man börjar från närmaste medurspunkt, med 0 som motsvarar ett långt avstånd och 1 som motsvarar ett kort avstånd. $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))$
Ett oändligt Fibonacci-ord kan innehålla 3 på varandra följande identiska underord, men aldrig 4 sådana underord. Det kritiska indexet för ett oändligt Fibonacci-ord är lika med upprepningar [5] . Detta är det minsta indexet (eller kritiska indexet) bland alla Sturm-ord. $2+\phi =3.618$
Det oändliga Fibonacci-ordet nämns ofta som det värsta fallet för algoritmer för upptäckt av strängupprepning
Ett oändligt Fibonacci-ord är ett morfiskt ord bildat av {0,1}* av endomorfismen 0 → 01, 1 → 0 [6] .

Applikationer

Fibonacci-ordkonstruktioner används för att modellera fysiska system med icke-periodisk ordning, såsom kvasikristaller , och för att studera ljusspridningsegenskaperna hos kristaller med Fibonacci-lager [7] .

Se även

Matematik och konst
Ordet tribonacci

Anteckningar

↑ En sekvens kallas slutligen periodisk med parametrar om villkoret för , var och är heltal, , . Det minsta talet kallas sekvensens period. En sekvens kallas -periodisk om ( Lipnitsky och 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 , sid. 443.
↑ Lothaire, 2011 , sid. 47.
↑ de Luca (1995) .
↑ Allouche, Shallit, 2003 , sid. 37.
↑ Lothaire, 2011 , sid. elva.
↑ Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987 .

Litteratur

Jean-Paul Allouche, Jeffrey Shallit. Automatiska sekvenser: teori, tillämpningar, generaliseringar. - Cambridge University Press , 2003. - ISBN 978-0-521-82332-6 .
Dharma-wardana MWC, MacDonald AH, Lockwood DJ, Baribeau J.-M., Houghton DC Raman sprider i Fibonacci-supergitter // Physical Review Letters . - 1987. - T. 58 . - S. 1761-1765 . - doi : 10.1103/physrevlett.58.1761 .
Lothaire M. Combinatorics on Words. — 2:a. - Cambridge University Press , 1997. - V. 17. - (Encyclopedia of Mathematics and Its Applications). - ISBN 0-521-59924-5 .
Lothaire M. Algebraisk kombinatorik på ord. - Cambridge University Press , 2011. - V. 90. - (Encyclopedia of Mathematics and its Applications). . Nytryck av 2002 års inbunden bok.
Aldo de Luca. En divisionsegenskap för Fibonacci-ordet // Information Processing Letters . - 1995. - T. 54 , nr. 6 . — S. 307–312 . - doi : 10.1016/0020-0190(95)00067-M .
Mignosi F., Pirillo G. Upprepningar i Fibonaccis oändliga ord // Informatique théorique et application. - 1992. - T. 26 , nr. 3 . — S. 199–204 .
Boris Adamczewski, Yann Bugeaud. Kapitel 8. Transcendens och diofantapproximation // Kombinatorik, automater och talteori / Valérie Berthé, Michael Rigo. - Cambridge: Cambridge University Press , 2010. - V. 135. - S. 443. - (Encyclopedia of Mathematics and its Applications). - ISBN 978-0-521-51597-9 .
Lipnitsky V. A., Chesalin N. V. Linjära koder och kodsekvenser: lärobok-metod. Manual för studenter mek.-mat. Fak. BGU . - Minsk: BGU, 2008.

Länkar

En detaljerad och tillgänglig beskrivning, på Ron Knotts webbplats
Weisstein, Eric W. Rabbit Sequence (engelska) på Wolfram MathWorld- webbplatsen .
YouTube -video _