Fibonacciho slovo

Fibonacciho slovo je specifická posloupnost binárních číslic (nebo obecněji jakýchkoliv dvou symbolů). Fibonacciho slovo získáme podobně jako Fibonacciho číslo, pouze namísto sčítání použijeme zřetězení slov.

Definice

Nechť S₀ = 0 a S₁ = 01. Nyní můžeme definovat obecný člen posloupnosti Fibonacciho slov: S_n = S_n-1S_n-2 (pro n > 1). Slovně řečeno – n-tý prvek této posloupnosti získáme tak, že zřetězíme jeho předchozí dva prvky. Fibonacciho slov je nekonečně mnoho.

Nekonečné Fibonacciho slovo označujeme S_∞.

Fibonacciho slova

Takže nyní máme takovouto posloupnost:

S0 = 0
S1 = 01
S2 = 010
S3 = 01001
S4 = 01001010
S5 = 0100101001001
…

Posloupnost několika prvních číslic z Fibonacciho slov by vypadala takto:

0100101001001010010100100101001001…

(Posloupnost A003849 v databázi On-Line Encyclopedia of Integer Sequences.) Tato posloupnost zároveň tvoří slovo S_∞.

Pravidla substituce

Jiné možnosti, jak definovat následující člen posloupnosti:

• Pokud známe slovo S_n a chceme získat slovo S_n+1, můžeme v S_n nahradit každý výskyt číslice 0 dvojicí 01 a každý výskyt číslice 1 nahradit číslicí 0. Příklad: máme S₃ = 01001. Provedeme záměny 0→01 a 1→0 (musíme je provést zároveň, pokud bychom nejprve provedli první záměnu a na tento výsledek aplikovali druhou záměnu, získáme posloupnost samých nul.)

0→01
1→0
0→01
0→01
1→0

Výsledek je 01001010. To odpovídá S₄, které je spočítáno výše.

• Fibonacciho slova můžeme přímo generovat pomoci posouváním kurzoru. Na začátku namíříme kurzor na první číslici slova. Pokud nyní kurzor míří na 0, přidáme na konec slova dvojici 01. Pokud kurzor míří na 1, přidáme na konec slova 0. Po přidání posuneme kurzor o jednu číslici doprava a opakujeme. Ve chvíli, kdy dojdeme na konec (původního) slova, proces končí a máme další člen posloupnosti. Mějme opět S₃ = 01001. Celý postup by vypadal takto:

  01001 => (Inicializace, nalevo původní slovo, napravo nové slovo – zatím prázdné, kurzor mimo číslice.)
 ^

 01001 => 01
 ^

 01001 => 010
  ^
 
 01001 => 01001
   ^

 01001 => 0100101
    ^

 01001 => 01001010
     ^

Pokud bychom tento postup aplikovali na jednom slovu (kurzor by se pohyboval po stejném slovu, k jakému by se přidávaly číslice), vygenerovali bychom v nekonečnu S_∞.

Další vlastnosti

• Slovo S_n má délku F_n-2, kde F představuje Fibonacciho posloupnost.
• S_∞ nemá periodu.
• Poslední dvě číslice v každém Fibonacciho slově (krom prvního) jsou buď 01, nebo 10.
• Přidáním dvou posledních číslic ze slova S_n v opačném pořadí na začátek slova vytvoříme palindrom. Například: S₃ = 01001 → 10 + 01001 = 1001001 a to je palindrom.
• Odmazáním dvou posledních číslic také získáme palindrom. Příklad: S₄ = 01001010 → 010010.
• V S_∞ platí, že (počet číslic)/(počet nul) = zlatý řez.
• S_∞ můžeme nazvat „vyrovnaným“ slovem. Pokud vezmeme dva libovolné podřetězce délky n, počet nul v těchto podřetězcích se bude lišit nejvýše o jedna.
• V žádném slově nenalezneme podřetězce 11 nebo 000.
• S_∞ obsahuje k+1 různých podřetězců délky k.
• S_∞ je rekurentní slovo – každý podřetězec je v S_∞ obsažen nekonečně krát.
• Pokud je u podřetězec S_∞, pak i obrácené slovo u^R je podřetězec S_∞.

Související články

• Fibonacciho posloupnost
• Fibonoriál
• Leonardo Fibonacci

Reference

V tomto článku byl použit překlad textu z článku Fibonacci word na anglické Wikipedii.