Fibonaccin sana

Fibonacci-sana on jokin binäärinumeroiden sarja (tai symbolit mistä tahansa kaksikirjaimisesta aakkosesta ). Fibonacci-sana muodostetaan toistuvalla ketjutuksella samalla tavalla kuin Fibonacci-luvut muodostetaan toistuvilla lisäyksillä.

Sana Fibonacci on oppikirjaesimerkki sanasta Sturm .

Nimeä "Fibonacci-sana" käytetään myös osoittamaan muotokielen L jäseniä , jotka sisältävät nollia ja ykkösiä ilman vierekkäisiä. Mikä tahansa tietyn Fibonacci-sanan osa kuuluu L -sanaan , mutta kielessä on monia muita merkkijonoja. L : ssä kunkin mahdollisen pituuden merkkijonojen lukumäärä on Fibonacci-luku.

Määritelmä

Olkoon se yhtä suuri kuin "0" ja yhtä suuri kuin "01". Nyt (edellisen jäsenen ja sitä edeltävän jäsenen ketjutus). $S_{0}$ $S_{1}$ ${\displaystyle S_{n}=S_{n-1}S_{n-2))$

Ääretön Fibonacci-sana on rajana . ${\displaystyle S_{\infty ))$

Listaamalla sekvenssin jäsenet yllä olevasta määritelmästä saadaan:

$S_{0}$ 0

$S_{1}$ 01

$S_{2}$ 010

$S_{3}$ 01001

$S_4$ 01001010

$S_5$ 0100101001001

…

Äärettömän Fibonacci-sanan ensimmäiset elementit ovat:

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, … ( sekvenssi A003849 OEIS : ssä )

Suljetun muodon lauseke tietyille numeroille

Sanan numerolla n oleva numero on yhtä suuri kuin , jossa on kultainen suhde , ja se on funktio "lattia" ("lattia"). $2+\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor$ $\varphi$ $\left\lfloor x\right\rfloor$

Korvaussäännöt

Toinen tapa siirtyä S n :stä S n + 1 :een on korvata jokainen 0 S n :ssä parilla 0, 1 ja korvata kukin 1 nollalla.

Vaihtoehtoisesti voidaan kuvitella generoivan koko äärettömän Fibonacci-sanan seuraavalla prosessilla. Aloitamme merkillä 0, asetamme kohdistimen sen päälle. Jokaisessa vaiheessa, jos kohdistin osoittaa 0:aan, lisää sanan loppuun 1 ja 0, ja jos kohdistin osoittaa 1:een, lisää 0 sanan loppuun. Kummassakin tapauksessa vaihe suoritetaan siirtämällä yksi asento oikealle.

Samanlainen ääretön sana, jota joskus kutsutaan kultaiseksi merkkijonoksi tai kanisekvenssiksi , muodostetaan samanlaisella äärettömällä prosessilla, mutta korvaussääntö on erilainen - jos kohdistin osoittaa 0:aan, lisää 1 ja jos se osoittaa 1:een, lisää 0, 1. Tuloksena oleva sarja alkaa merkillä

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

Tämä sekvenssi eroaa kuitenkin Fibonacci-sanasta triviaalisesti - nollat korvataan ykkösillä ja koko sekvenssiä siirretään yhdellä.

Kultaisen merkkijonon suljettu muotolauseke on:

Sanan numerolla n oleva numero on yhtä suuri kuin , jossa on kultainen leikkaus , ja se on "lattia"-funktio . $\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1$ $\varphi$ $\left\lfloor x\right\rfloor$

Keskustelu

Sana liittyy kuuluisaan samannimiseen sekvenssiin ( Fibonacci-sekvenssi ), koska kokonaislukujen lisääminen induktiivisessa määritelmässä korvataan merkkijonojen ketjutuksella. Tämä johtaa siihen, että S n :n pituus on F n + 2 , ( n + 2) Fibonacci-luku. Myös ykkösten lukumäärä S n :ssä on F n ja nollien määrä S n :ssä on F n + 1 .

Muut ominaisuudet

Ääretön Fibonacci-sana ei ole jaksollinen eikä lopulta jaksollinen [1] .
Fibonacci-sanan kaksi viimeistä numeroa ovat joko "01" tai "10".
Kun Fibonacci-sanan kaksi viimeistä kirjainta poistetaan tai kaksi viimeistä kirjainta lisätään komplementin alkuun, syntyy palindromi . Esimerkki: 01 =0101001010 on palindromi. Äärettömän Fibonacci-sanan palindrominen tiheys on 1/φ, missä φ on kultainen suhde . Tämä on suurin mahdollinen arvo ei-jaksollisille sanoille [2] . $S_4$
Äärettömässä Fibonacci-sanassa suhde (numeroiden lukumäärä)/(nollien lukumäärä) on yhtä suuri kuin φ, samoin kuin nollien lukumäärän suhde ykkösten lukumäärään.
Ääretön Fibonacci-sana on tasapainotettu sekvenssi . Ota kaksi samanpituista osamerkkijonoa mistä tahansa Fibonacci-sanan kohdasta. Niiden Hamming-painojen erotus (yksiköiden lukumäärä) ei koskaan ylitä yhtä [3] .
Alasanat 11 ja 000 eivät koskaan esiinny.
Äärettömän Fibonacci-sanan monimutkaisuusfunktio on n + 1 — se sisältää n + 1 erillistä osasanaa, joiden pituus on n . Esimerkki: On 4 erilaista alisanaa, joiden pituus on 3: "001", "010", "100" ja "101". Koska sana on ei-jaksollinen, sillä on "minimimutkaisuus", ja siksi se on Sturm-sana [4] , jonka kaltevuus on. Ääretön Fibonacci-sana on standardisana , joka muodostuu direktiivisekvenssistä (1,1,1,….). $1/\phi ^{2}$
Ääretön Fibonacci-sana on toistuva. Eli mikä tahansa alisana esiintyy äärettömän usein.
Jos on alisana äärettömästä Fibonacci-sanasta, niin alisana on sen käänteinen, merkitty . $u$ ${\displaystyle u^{R))$
Jos on äärettömän Fibonacci-sanan alisana, niin pienin jakso on Fibonacci-luku. $u$ $u$
Kahden Fibonacci-sanojen ketjuttaminen on "melkein kommutatiivista". ja eroavat vain kahdesta viimeisestä kirjaimesta. ${\displaystyle S_{n+1}=S_{n}S_{n-1))$ ${\displaystyle S_{n-1}S_{n))$
Seurauksena on, että ääretön Fibonacci-luku voidaan kuvata suoran osien sarjalla, jonka kaltevuus tai . Katso kuva yllä. $\phi$ $\phi-1$
Luku 0,010010100…, jonka desimaaliluvut ovat äärettömän Fibonacci-sanan numeroita, on transsendentaalinen .
Kirjaimet "1" löytyvät ylemmän Wythoff-sekvenssin ( OEIS A001950) peräkkäisten arvojen antamista kohdista: $\lfloor n\phi ^{2}\rfloor$
Kirjaimet "0" löytyvät alemman Wythoff-sekvenssin (OEIS A000201) peräkkäisten arvojen antamista kohdista: $\lfloor n\phi \rfloor$
Pistejakauma yksikköympyrässä peräkkäin myötäpäivään kultaisessa kulmassa muodostaa kahden pituisen kuvion yksikköympyrään. Vaikka edellä kuvattu Fibonaccin sananmuodostusprosessi ei suoraan vastaa ympyrän osien peräkkäistä jakoa, tämä kuvio on sama kuin aloitettaessa lähimmästä myötäpäivään pisteestä, jossa 0 vastaa pitkää matkaa ja 1 vastaa lyhyttä etäisyyttä. ${\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))$
Ääretön Fibonacci-sana voi sisältää kolme peräkkäistä identtistä alisanaa, mutta ei koskaan neljää tällaista alisanaa. Kriittinen indeksi äärettömälle Fibonacci-sanalle on yhtä suuri kuin toistot [5] . Tämä on pienin indeksi (tai kriittinen indeksi) kaikista Sturm-sanoista. $2+\phi =3,618$
Ääretön Fibonacci - sana mainitaan usein merkkijonon toiston havaitsemisalgoritmien pahimpana tapauksena
Ääretön Fibonacci-sana on morfinen sana , joka on muodostettu sanasta {0,1}* endomorfismilla 0 → 01, 1 → 0 [6] .

Sovellukset

Fibonacci-sanakonstruktioita käytetään mallintamaan fyysisiä järjestelmiä, joissa on ei-jaksollinen järjestys, kuten kvasikiteitä , ja tutkimaan kiteiden valonsirontaominaisuuksia Fibonacci-kerroksilla [7] .

Katso myös

Matematiikka ja kuvataide
Sana tribonacci

Muistiinpanot

↑ Sekvenssiä kutsutaan lopuksi jaksolliseksi parametreilla , jos ehto , jossa ja ovat kokonaislukuja, , . Pienintä tällaista lukua kutsutaan sekvenssin jaksoksi. Sekvenssiä kutsutaan -jaksolliseksi if ( Lipnitsky ja Chesalin 2008 , s. 27). $v=(v_{0},v_{1},\ldots )$ ${\näyttötyyli (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. yksitoista.
↑ Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987 .

Kirjallisuus

Jean-Paul Allouche ja Jeffrey Shallit. Automaattiset sekvenssit: teoria, sovellukset, yleistykset. - Cambridge University Press , 2003. - ISBN 978-0-521-82332-6 .
Dharma-wardana MWC, MacDonald AH, Lockwood DJ, Baribeau J.-M., Houghton DC Ramanin sironta Fibonacci-superhiloissa // Physical Review Letters . - 1987. - T. 58 . - S. 1761-1765 . - doi : 10.1103/physrevlett.58.1761 .
Lothaire M. Kombinatoriikka sanoista. – 2. - Cambridge University Press , 1997. - V. 17. - (Encyclopedia of Mathematics and Its Applications). - ISBN 0-521-59924-5 .
Lothaire M. Sanojen algebrallinen kombinatoriikka. - Cambridge University Press , 2011. - V. 90. - (Encyclopedia of Mathematics and Its Applications). . Uusintapainos 2002 kovakantinen.
Aldo de Luca. Fibonacci-sanan jakoominaisuus // Information Processing Letters . - 1995. - T. 54 , no. 6 . — S. 307–312 . - doi : 10.1016/0020-0190(95)00067-M .
Mignosi F., Pirillo G. Toistoja Fibonaccin äärettömässä sanassa // Informatique théorique et application. - 1992. - T. 26 , no. 3 . — S. 199–204 .
Boris Adamczewski, Yann Bugeaud. Luku 8. Transsendenssi ja diofantiiniapproksimaatio // Kombinatoriikka, automaatit ja lukuteoria / 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. Lineaariset koodit ja koodisekvenssit: oppikirja-menetelmä. Opiskelijoiden käsikirja mek.-matto. Fak. BGU . - Minsk: BGU, 2008.

Linkit

Yksityiskohtainen ja helposti saatavilla oleva kuvaus Ron Knottin sivustolla
Weisstein, Eric W. Rabbit Sequence (englanniksi) Wolfram MathWorld -verkkosivustolla .
YouTube video _