Fibonacci ord

Fibonacci-ordet er en sekvens af binære cifre (eller symboler fra et hvilket som helst alfabet med to bogstaver ) . Fibonacci-ordet er dannet ved gentagen sammenkædning på samme måde, som Fibonacci-tal er dannet ved gentagne tilføjelser.

Ordet Fibonacci er et lærebogseksempel på ordet Sturm .

Navnet "Fibonacci-ord" bruges også til at betegne medlemmer af det formelle sprog L , som indeholder strenge af nuller og ener uden tilstødende. Enhver del af et bestemt Fibonacci-ord hører til L , men der er mange andre strenge i sproget. I L er antallet af strenge af hver mulig længde et Fibonacci-tal.

Definition

Lad det være lig med "0" og lig med "01". Nu (sammenkædning af det forrige medlem og medlemmet før det). $S_{0}$ $S_{1}$ ${\displaystyle S_{n}=S_{n-1}S_{n-2))$

Det uendelige Fibonacci-ord er grænsen . ${\displaystyle S_{\infty ))$

Liste over medlemmerne af sekvensen fra definitionen ovenfor giver:

$S_{0}$ 0

$S_{1}$ 01

$S_{2}$ 010

$S_{3}$ 01001

$S_4$ 01001010

$S_5$ 0100101001001

…

De første par elementer i det uendelige Fibonacci-ord er:

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 )

Udtryk i lukket form for specifikke cifre

Cifferet med ordet n er lig med , hvor er det gyldne snit , og er funktionen "gulv" ("gulv"). $2+\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor$ $\varphi$ $\left\lfloor x\right\rfloor$

Udskiftningsregler

En anden måde at gå fra S n til S n + 1 er at erstatte hver 0 i S n med et par 0, 1 og erstatte hver 1 med et 0.

Alternativt kan man forestille sig at generere hele det uendelige Fibonacci-ord med følgende proces. Vi starter med tegnet 0, vi placerer markøren på det. Ved hvert trin, hvis markøren peger på 0, skal du tilføje 1 og 0 til slutningen af ordet, og hvis markøren peger på 1, skal du tilføje 0 til slutningen af ordet. I begge tilfælde fuldføres trinnet ved at flytte en position til højre.

Et lignende uendeligt ord, nogle gange kaldet en gylden streng eller en kaninsekvens , er dannet af en lignende uendelig proces, men substitutionsreglen er anderledes - hvis markøren peger på 0, tilføj 1, og hvis den peger på 1, tilføj 0, 1. Den resulterende sekvens starter 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, …

Denne sekvens adskiller sig dog trivielt fra Fibonacci-ordet - nuller erstattes af etaller, og hele sekvensen forskydes med én.

Det lukkede formudtryk for den gyldne streng er:

Cifferet med ordet n er lig med , hvor er det gyldne snit , og er "gulv"-funktionen . $\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1$ $\varphi$ $\left\lfloor x\right\rfloor$

Diskussion

Ordet er relateret til den berømte sekvens af samme navn ( Fibonacci-sekvensen ), idet tilføjelsen af heltal i den induktive definition er erstattet af strengsammenkædning. Dette resulterer i, at længden af S n er F n + 2 , det ( n + 2). Fibonacci-tal. Også antallet af enere i S n er F n , og antallet af nuller i S n er F n + 1 .

Andre egenskaber

Det uendelige Fibonacci-ord er ikke periodisk og er ikke endeligt periodisk [1] .
De sidste to cifre i Fibonacci-ordet er enten "01" eller "10".
Fjernelse af de sidste to bogstaver i Fibonacci-ordet eller tilføjelse af de sidste to bogstaver til begyndelsen af komplementet skaber et palindrom . Eksempel: 01 =0101001010 er et palindrom. Den palindromiske tæthed af et uendeligt Fibonacci-ord er 1/φ, hvor φ er det gyldne snit . Dette er den størst mulige værdi for ikke-periodiske ord [2] . $S_4$
I et uendeligt Fibonacci-ord er forholdet (antal cifre)/(antal nuller) lig med φ, ligesom forholdet mellem antallet af nuller og antallet af enere.
Det uendelige Fibonacci-ord er en afbalanceret sekvens . Tag to understrenge af samme længde hvor som helst i Fibonacci-ordet. Forskellen mellem deres Hamming-vægte (antal enheder) overstiger aldrig 1 [3] .
Underord 11 og 000 forekommer aldrig.
Kompleksitetsfunktionen et uendeligt Fibonacci-ord er n + 1 — det indeholder n + 1 distinkte underord af længden n . Eksempel: Der er 4 forskellige underord af længde 3: "001", "010", "100" og "101". Da ordet er en ikke-periodisk sekvens, har ordet "minimum kompleksitet", og er derfor et Sturm-ord [4] med hældning. Et uendeligt Fibonacci-ord er et standardord dannet af direktivsekvensen (1,1,1,….). $1/\phi ^{2}$
Det uendelige Fibonacci-ord er tilbagevendende. Det vil sige, at ethvert underord forekommer uendeligt ofte.
Hvis er et underord af et uendeligt Fibonacci-ord, så er underordet dets inverse, betegnet med . $u$ $u^{R}$
Hvis er et underord til et uendeligt Fibonacci-ord, så er den mindste periode et Fibonacci-tal. $u$ $u$
Sammenkædningen af to sekvenser af Fibonacci-ord er "næsten kommutativ". og afviger kun i de sidste to bogstaver. ${\displaystyle S_{n+1}=S_{n}S_{n-1))$ ${\displaystyle S_{n-1}S_{n))$
Som en konsekvens kan et uendeligt Fibonacci-tal beskrives ved en sekvens af sektioner af en lige linje med en hældning eller . Se billedet ovenfor. $\phi$ $\phi -1$
Tallet 0,010010100…, hvis decimaltal er cifrene i det uendelige Fibonacci-ord, er transcendentalt .
Bogstaverne "1" kan findes i positioner givet af successive værdier af den øvre Wythoff-sekvens ( OEIS A001950): $\lfloor n\phi ^{2}\rfloor$
Bogstaverne "0" kan findes i positioner givet af successive værdier af den nedre Wythoff-sekvens (OEIS A000201): $\lfloor n\phi \rfloor$
En fordeling af punkter på enhedscirklen , placeret sekventielt med uret i den gyldne vinkel , danner et mønster med to længder på enhedscirklen. Selvom Fibonacci-orddannelsesprocessen, der er beskrevet ovenfor, ikke direkte svarer til den sekventielle opdeling af cirkelsegmenter, er dette mønster lig , når man starter fra det nærmeste punkt med uret, med 0 svarende til en lang afstand og 1 svarende til en kort afstand. $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))$
Et uendeligt Fibonacci-ord kan indeholde 3 på hinanden følgende identiske underord, men aldrig 4 sådanne underord. Det kritiske indeks for et uendeligt Fibonacci-ord er lig med gentagelser [5] . Dette er det mindste indeks (eller kritiske indeks) blandt alle Sturm-ord. $2+\phi =3.618$
Det uendelige Fibonacci-ord nævnes ofte som det værste tilfælde for gentagelsesalgoritmer for strenge
Et uendeligt Fibonacci-ord er et morfisk ord dannet af {0,1}* af endomorfien 0 → 01, 1 → 0 [6] .

Ansøgninger

Fibonacci-ordkonstruktioner bruges til at modellere fysiske systemer med ikke-periodisk orden, såsom kvasikrystaller , og til at studere lysspredningsegenskaberne for krystaller med Fibonacci-lag [7] .

Se også

Matematik og billedkunst
Ordet tribonacci

Noter

↑ En sekvens kaldes endelig periodisk med parametre, hvis betingelsen for , hvor og er heltal, , . Det mindste sådant tal kaldes sekvensens periode. En sekvens kaldes -periodisk hvis ( Lipnitsky og 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 , s. 443.
↑ Lothaire, 2011 , s. 47.
↑ de Luca (1995) .
↑ Allouche, Shallit, 2003 , s. 37.
↑ Lothaire, 2011 , s. elleve.
↑ Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987 .

Litteratur

Jean-Paul Allouche, Jeffrey Shallit. Automatiske sekvenser: Teori, applikationer, generaliseringer. - Cambridge University Press , 2003. - ISBN 978-0-521-82332-6 .
Dharma-wardana MWC, MacDonald AH, Lockwood DJ, Baribeau J.-M., Houghton DC Raman-spredning i Fibonacci-supergitter // Physical Review Letters . - 1987. - T. 58 . - S. 1761-1765 . - doi : 10.1103/physrevlett.58.1761 .
Lothaire M. Combinatorics on Words. — 2. - 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). . Genoptryk af hardbacken fra 2002.
Aldo de Luca. En divisionsegenskab for Fibonacci-ordet // Information Processing Letters . - 1995. - T. 54 , no. 6 . — S. 307–312 . - doi : 10.1016/0020-0190(95)00067-M .
Mignosi F., Pirillo G. Gentagelser i Fibonaccis uendelige ord // Informatique théorique et application. - 1992. - T. 26 , no. 3 . — S. 199–204 .
Boris Adamczewski, Yann Bugeaud. Kapitel 8. Transcendens og diofantisk tilnærmelse // Kombinatorik, automater og 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. Lineære koder og kodesekvenser: lærebogsmetode. Manual for studerende mek.-mat. Fak. BGU . - Minsk: BGU, 2008.