Fibonacci word

Fibonacci word

The Fibonacci word is a specific infinite sequence of binary digits (or symbols from any two-letter alphabet).

Definition

Let S_0 be "0" and S_1 be "01". Now S_n = S_{n-1}S_{n-2} (the concatenation of the previous sequence and the one before that). The Fibonacci word is the limit S_{infty}.

The sequence

We have:

S_0 0

S_1 0, 1

S_2 0, 1, 0

S_3 0, 1, 0, 0, 1

S_4 0, 1, 0, 0, 1, 0, 1, 0

S_5 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1

...

The first few elements of the sequence are:

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

Closed-form expression for individual digits

The nth digit of the word is leftlfloor {left( {n + 2} ight),{varphi over {1 + 2,varphi } ight floor - leftlfloor {left( {n + 1} ight),{varphi over {1 + 2,varphi } ight floor and varphi is the golden ratio and leftlfloor x ight floor is the floor function (see [http://www.research.att.com/~njas/sequences/A3849 OEIS' A3849] ).

Substitution rules

Another way of going from "S""n" to "S""n" + 1 is to replace each symbol 0 in "S""n" with the pair of consecutive symbols 0, 1 in "S""n" + 1, and to replace each symbol 1 in "S""n" with the single symbol 0 in "S""n" + 1.

Alternatively, one can imagine directly generating the entire Fibonacci word by the following process: start with a cursor pointing to the single digit 0. Then, at each step, if the cursor is pointing to a 0, append 1, 0 to the end of the word, and if the cursor is pointing to a 1, append 0 to the end of the word. In either case, complete the step by moving the cursor one position to the right.

A similar infinite word, sometimes called the rabbit sequence, is generated by a similar infinite process with a different replacement rule: whenever the cursor is pointing to a 0, append 1, and whenever the cursor is pointing to a 1, append 0, 1. The resulting sequence begins: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, ...However this sequence differs from the Fibonacci word only trivially, by swapping 0's for 1's and shifting the positions by one.

Discussion

The word is related to the famous sequence of the same name (the Fibonacci sequence) in the sense that addition of integers in the inductive definition is replaced with string concatenation. This causes the length of "S""n" to be "F""n" + 2, the ("n" + 2)th Fibonacci number. Also the number of 1s in "S""n" is "F""n" + 1 and the number of 0s in "S""n" is "F""n".

The Fibonacci word is a famous example of a Sturmian word.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Fibonacci — Infobox Scientist box width = 300px name = Leonardo of Pisa (Fibonacci) image width = 150px caption = Leonardo of Pisa, Fibonacci birth date = c. 1170 birth place = Pisa, Italy death date = c. 1250 death place = Pisa, Italy residence = Italy… …   Wikipedia

  • Fibonacci number — A tiling with squares whose sides are successive Fibonacci numbers in length …   Wikipedia

  • Fibonacci coding — In mathematics, Fibonacci coding is a universal code which encodes positive integers into binary code words. All tokens end with 11 and have no 11 before the end. The formula used to generate Fibonacci codes is: #N = sum {i=0}^k d(i) F(i) #d(i) …   Wikipedia

  • Mot de Fibonacci — Un mot de Fibonacci est une suite spécifique de lettres ou symboles pris dans un alphabet quelconque de deux lettres. Les mots de Fibonacci sont à l opération de concaténation ce que les nombres de Fibonacci sont à l addition. Caractérisation par …   Wikipédia en Français

  • Fractale du mot de Fibonacci — Les trois types de courbes fractales du mot de Fibonacci. La fractale du mot de Fibonacci est une courbe fractale définie dans le plan à partir du mot de Fibonacci. Sommaire 1 …   Wikipédia en Français

  • Sturmian word — In mathematics, a Sturmian word, named after Jacques Charles François Sturm, is a certain kind of infinite word. Contents 1 Definition 2 Discussion 3 History 4 Re …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • Liste De Fractales Par Dimension De Hausdorff — Cet article est une liste de fractales, ordonnées par dimension de Hausdorff croissante. En mathématiques, une fractale est un ensemble dont la dimension de Hausdorff (notée δ) est strictement supérieure à la dimension topologique[1]. Sommaire 1… …   Wikipédia en Français

  • Liste de fractales — par dimension de Hausdorff Cet article est une liste de fractales, ordonnées par dimension de Hausdorff croissante. En mathématiques, une fractale est un ensemble dont la dimension de Hausdorff (notée δ) est strictement supérieure à la dimension… …   Wikipédia en Français

  • Liste de fractales par dimension de Hausdorff — Cet article est une liste de fractales, ordonnées par dimension de Hausdorff croissante. En mathématiques, une fractale est un ensemble dont la dimension de Hausdorff (notée δ) est strictement supérieure à la dimension topologique[1]. Sommaire 1… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”