Fibonacci szó

A Fibonacci szó bináris számjegyek sorozata (vagy bármely kétbetűs ábécé szimbóluma ). A Fibonacci szó ismételt összefűzéssel jön létre ugyanúgy, mint a Fibonacci számok ismételt összeadással.

A Fibonacci szó a Sturm szó tankönyvi példája .

A "Fibonacci-szó" elnevezést használják az L formális nyelv tagjainak megjelölésére is , amely nullákból álló karakterláncokat és egyeseket egymás melletti karakterláncok nélkül tartalmaz. Egy adott Fibonacci szó bármely része L -hez tartozik , de sok más karakterlánc is létezik a nyelvben. L -ben az egyes lehetséges hosszúságú karakterláncok száma Fibonacci-szám.

Definíció

Legyen egyenlő "0", és egyenlő "01". Most (az előző tag és az előtte lévő tag összefűzése). $S_{0}$ $S_{1}$ ${\displaystyle S_{n}=S_{n-1}S_{n-2))$

A végtelen Fibonacci szó a határ . ${\displaystyle S_{\infty ))$

A sorozat tagjainak felsorolása a fenti definícióból a következőt kapja:

$S_{0}$ 0

$S_{1}$ 01

$S_{2}$ 010

$S_{3}$ 01001

$S_4$ 01001010

$S_5$ 0100101001001

…

A végtelen Fibonacci szó első néhány eleme:

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, … ( A003849 sorozat az OEIS -ben )

Zárt formájú kifejezés meghatározott számjegyekhez

A szó n számú számjegye egyenlő , ahol az aranymetszés , és a "floor" ("floor") függvény. $2+\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor$ $\varphi$ $\left\lfloor x\right\rfloor$

Helyettesítési szabályok

Egy másik módja annak, hogy S n -ről S n + 1 -re lépjünk, ha az S n - ben minden 0-t 0, 1 párra cserélünk, és mindegyik 1-et 0-ra cserélünk.

Alternatív megoldásként elképzelhető, hogy a teljes végtelen Fibonacci szót a következő eljárással generáljuk. A 0 karakterrel kezdjük, ráhelyezzük a kurzort. Ha a kurzor 0-ra mutat, minden lépésnél adjon hozzá 1-et és 0-t a szó végéhez, és ha a kurzor 1-re mutat, adjon 0-t a szó végéhez. Mindkét esetben a lépést egy pozícióval jobbra mozgatással fejezzük be.

Hasonló végtelen szó, amelyet néha aranyfüzérnek vagy nyúl sorozatnak neveznek , hasonló végtelen folyamattal jön létre, de a helyettesítési szabály más - ha a kurzor 0-ra mutat, adjunk hozzá 1-et, ha pedig 1-et, adjunk hozzá 0-t, 1. A kapott sorozat a következővel kezdődik:

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

Ez a sorozat azonban triviálisan különbözik a Fibonacci szótól - a nullákat egyesek helyettesítik, és a teljes sorozatot eggyel eltolja.

Az arany húr zárt formájú kifejezése:

A szó n számú számjegye egyenlő a , ahol az aranymetszés , és a „padló” függvény . $\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1$ $\varphi$ $\left\lfloor x\right\rfloor$

Vita

A szó rokon az azonos nevű híres sorozattal ( a Fibonacci-szekvencia ), mivel az induktív definícióban az egész számok összeadását karakterlánc-összefűzéssel helyettesíti. Ez azt eredményezi, hogy S n hossza F n + 2 , az ( n + 2)-edik Fibonacci-szám. Ezenkívül az egyesek száma S n - ben F n , és a nullák száma S n - ben F n + 1 .

Egyéb tulajdonságok

A végtelen Fibonacci szó nem periodikus és végül nem is periodikus [1] .
A Fibonacci szó utolsó két számjegye "01" vagy "10".
Ha eltávolítja a Fibonacci szó utolsó két betűjét, vagy hozzáadja az utolsó két betűt a kiegészítés elejéhez, akkor egy palindrom jön létre . Példa: 01 =0101001010 egy palindrom. Egy végtelen Fibonacci szó palindrom sűrűsége 1/φ, ahol φ az aranymetszés . Ez a nem periodikus szavak lehetséges legnagyobb értéke [2] . $S_4$
Egy végtelen Fibonacci-szóban az arány (számjegyek száma)/(nullák száma) egyenlő φ-vel, csakúgy, mint a nullák számának az egyesek számának aránya.
A végtelen Fibonacci szó egy kiegyensúlyozott sorozat . Vegyünk két azonos hosszúságú részstringet bárhol a Fibonacci szóban. A Hamming-súlyuk (egységek száma) közötti különbség soha nem haladja meg az 1-et [3] .
A 11. és 000. részszavak soha nem fordulnak elő.
Egy végtelen Fibonacci-szó összetettségi függvénye n + 1 — n + 1 különálló, n hosszú részszót tartalmaz . Példa: 4 különböző, 3-as hosszúságú részszó létezik: "001", "010", "100" és "101". Mivel nem periodikus sorozat, a szó "minimális bonyolultságú", ezért Sturm szó [4] meredekséggel. A végtelen Fibonacci szó egy standard szó , amelyet (1,1,1,….) direktívasorozat alkot. $1/\phi ^{2}$
A végtelen Fibonacci szó visszatérő. Vagyis bármely részszó végtelenül gyakran előfordul.
Ha egy végtelen Fibonacci szó részszava, akkor az alszó az inverze, jelölése . $u$ ${\displaystyle u^{R))$
Ha egy végtelen Fibonacci-szó részszava, akkor a legkisebb periódus egy Fibonacci-szám. $u$ $u$
A Fibonacci-szavak két sorozatának összefűzése „majdnem kommutatív”. és csak az utolsó két betűben különböznek. ${\displaystyle S_{n+1}=S_{n}S_{n-1))$ ${\displaystyle S_{n-1}S_{n))$
Következésképpen egy végtelen Fibonacci-szám leírható egy egyenes metszetsorozatával, amelynek meredeksége vagy . Lásd a fenti képet. $\phi$ $\phi -1$
A 0,010010100… szám, amelynek decimális számjegyei a végtelen Fibonacci-szó számjegyei, transzcendentális .
Az "1" betűk a felső Wythoff-szekvencia ( OEIS A001950) egymást követő értékei által megadott pozíciókban találhatók: $\lfloor n\phi ^{2}\rfloor$
A "0" betűk az alsó Wythoff-szekvencia (OEIS A000201) egymást követő értékei által megadott pozíciókban találhatók: $\lfloor n\phi \rfloor$
A pontok eloszlása az egységkörön , az óramutató járásával megegyező irányban, az aranyszögben egymás után elhelyezve , két hosszúságú mintát képez az egységkörön. Bár a fent leírt Fibonacci szóalkotási folyamat közvetlenül nem felel meg a körszakaszok szekvenciális felosztásának, ez a mintázat megegyezik a legközelebbi óramutató járásával megegyező pontból indulva, ahol a 0 nagy távolságot, az 1 pedig egy rövid távolságot jelent. $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))$
Egy végtelen Fibonacci szó tartalmazhat 3 egymás utáni azonos részszót, de soha nem 4 ilyen részszót. Egy végtelen Fibonacci-szó kritikus indexe egyenlő az ismétlődésekkel [5] . Ez a legkisebb index (vagy kritikus index) az összes Sturm szó között. $2+\phi =3,618$
A végtelen Fibonacci szót gyakran a legrosszabb esetként emlegetik a karakterláncismétlést észlelő algoritmusok esetében
A végtelen Fibonacci-szó egy morfikus szó , amely a 0,1}*-ból a 0 → 01, 1 → 0 [6] endomorfizmussal alakul ki .

Alkalmazások

A Fibonacci szókonstrukciókat nem periodikus rendű fizikai rendszerek, például kvázikristályok modellezésére , valamint Fibonacci-rétegű kristályok fényszórási tulajdonságainak tanulmányozására használják [7] .

Lásd még

Matematika és képzőművészet
A tribonacci szó

Jegyzetek

↑ Egy sorozatot végleg periodikusnak nevezünk paraméterekkel , ha , ahol és feltétele egész számok, , . A legkisebb ilyen számot a sorozat periódusának nevezzük. Egy szekvenciát -periodikusnak nevezünk, ha ( Lipnitsky és Chesalin 2008 , 27. o.). $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 , p. 443.
↑ Lothaire, 2011 , p. 47.
↑ de Luca (1995) .
↑ Allouche, Shallit, 2003 , p. 37.
↑ Lothaire, 2011 , p. tizenegy.
↑ Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987 .

Irodalom

Jean-Paul Allouche, Jeffrey Shallit. Automatikus szekvenciák: elmélet, alkalmazások, általánosítások. - Cambridge University Press , 2003. - ISBN 978-0-521-82332-6 .
Dharma-wardana MWC, MacDonald AH, Lockwood DJ, Baribeau J.-M., Houghton DC Raman scattering in Fibonacci superlattices // Physical Review Letters . - 1987. - T. 58 . - S. 1761-1765 . - doi : 10.1103/physrevlett.58.1761 .
Lothaire M. Kombinatorika a szavakról. — 2. - Cambridge University Press , 1997. - V. 17. - (Matematika és alkalmazásai enciklopédiája). - ISBN 0-521-59924-5 .
Lothaire M. Algebrai kombinatorika a szavakról. - Cambridge University Press , 2011. - V. 90. - (Matematika és alkalmazásai enciklopédiája). . A 2002-es keménykötés utánnyomása.
Aldo de Luca. A Fibonacci szó felosztási tulajdonsága // Information Processing Letters . - 1995. - T. 54 , sz. 6 . – S. 307–312 . - doi : 10.1016/0020-0190(95)00067-M .
Mignosi F., Pirillo G. Ismétlések a Fibonacci végtelen szóban // Informatique théorique et application. - 1992. - T. 26 , sz. 3 . – S. 199–204 .
Boris Adamczewski, Yann Bugeaud. 8. fejezet Transzcendencia és diofantin közelítés // Kombinatorika, automaták és számelmélet / Valérie Berthé, Michael Rigo. - Cambridge: Cambridge University Press , 2010. - V. 135. - P. 443. - (Encyclopedia of Mathematics and its Applications). - ISBN 978-0-521-51597-9 .
Lipnitsky V. A., Chesalin N. V. Lineáris kódok és kódszekvenciák: tankönyv-módszer. Kézikönyv tanulóknak mech.-mat. Fak. BGU . - Minszk: BGU, 2008.

Linkek

Részletes és elérhető leírás Ron Knott oldalán
Weisstein, Eric W. Rabbit Sequence (angol) a Wolfram MathWorld webhelyen .
YouTube videó _