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}$

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

Bibliografia

• Lech Banachowski, Krzysztof Diks, Wojciech Rytter, Algorytmy i struktury danych, WNT, Warszawa, 1996, s. 169, ISBN 83-204-1995-6