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.

Definicja słów Fibonacciego

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

$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 $\cdot$ oznacza konkatenację.

Początkowe słowa Fibonacciego

$F_{1}=b$

$F_{2}=a$

$F_{3}=ab$

$F_{4}=aba$

$F_{5}=abaab$

$F_{6}=abaababa$

$F_{7}=abaababaabaab$

$F_{8}=abaababaabaababaababa$

$F_{9}=abaababaabaababaababaabaababaabaab$

Własności słów Fibonacciego

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

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

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

Zobacz też

• słowo Thuego-Morse’a

Uwagi

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

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

Bibliografia

• 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 .

Linki zewnętrzne

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