Słowa Fibonacciego

Słowa Fibonacciego – ciąg słów stosowany w informatyce teoretycznej między innymi do analizy złożoności algorytmów tekstowych.

Słowa Fibonacciego są słowami nad alfabetem ${\displaystyle \left\{a,b\right\}}$ zdefiniowany rekurencyjnie jako:

${\displaystyle F_{n}:={\begin{cases}b&{\mbox{dla }}n=1;\\a&{\mbox{dla }}n=2;\\F_{n-1}\cdot F_{n-2}&{\mbox{dla }}n>2.\end{cases}}}$

Gdzie symbol ${\displaystyle \cdot }$ oznacza konkatenację.

${\displaystyle F_{1}=b}$

${\displaystyle F_{2}=a}$

${\displaystyle F_{3}=ab}$

${\displaystyle F_{4}=aba}$

${\displaystyle F_{5}=abaab}$

${\displaystyle F_{6}=abaababa}$

${\displaystyle F_{7}=abaababaabaab}$

${\displaystyle F_{8}=abaababaabaababaababa}$

${\displaystyle F_{9}=abaababaabaababaababaabaababaabaab}$

${\displaystyle |F_{n}|=f_{n},}$ gdzie ${\displaystyle f_{n}}$ jest ${\displaystyle n}$-tą liczbą Fibonacciego.

Niech ${\displaystyle {\tilde {w}}}$ oznacza słowo ${\displaystyle w}$ z ostatnimi dwoma literami zamienionymi kolejnością. Zachodzi:

${\displaystyle {\tilde {F_{n}}}=F_{n-2}\cdot F_{n-1}}$

• słowo Thuego-Morse’a

Nie ma jednej konwencji dotyczącej oznaczania początkowych słów Fibonacciego. W niektórych źródłach przyjmuje się ${\displaystyle F_{0}=b,}$ ${\displaystyle F_{1}=a,}$ w innych z kolei ${\displaystyle F_{0}=a,}$ ${\displaystyle F_{1}=ab.}$

Alfabet ${\displaystyle \left\{a,b\right\}}$ nie jest konieczny (choć jest często używany). Można równie dobrze używać alfabetu ${\displaystyle \left\{0,1\right\}}$ lub innego dwuznakowego.

• LechL. Banachowski LechL., KrzysztofK. Diks KrzysztofK., WojciechW. Rytter WojciechW., Algorytmy i struktury danych, Warszawa: WNT, 1996, s. 169, ISBN 83-204-1995-6, OCLC 69370054 .

• Fibonacci word (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].