Namespaces
Variants
Actions

Difference between revisions of "Fibonacci word"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Fibonacci word)
 
m (link)
Line 10: Line 10:
 
$$
 
$$
  
The Fibonacci word has complexity $c_{\mathcal{F}}(n) = n+1$ and hence is a [[Sturmian sequence]].  It is a [[morphic word]], a fixed point of the endomorphism $a \mapsto ab$, $b \mapsto a$.
+
The Fibonacci word has [[complexity function]] $c_{\mathcal{F}}(n) = n+1$ and hence is a [[Sturmian sequence]].  It is a [[morphic word]], a fixed point of the endomorphism $a \mapsto ab$, $b \mapsto a$.
  
 
====References====
 
====References====
 
* Allouche, Jean-Paul; Shallit, Jeffrey ''Automatic Sequences: Theory, Applications, Generalizations,'' Cambridge University Press (2003) ISBN 978-0-521-82332-6 {{ZBL|1086.11015}}
 
* Allouche, Jean-Paul; Shallit, Jeffrey ''Automatic Sequences: Theory, Applications, Generalizations,'' Cambridge University Press (2003) ISBN 978-0-521-82332-6 {{ZBL|1086.11015}}
* Lothaire, M. ''Combinatorics on Words'' (2nd ed.) Encyclopedia of Mathematics and Its Applications '''17''''  Cambridge University Press (1997) ISBN 0-521-59924-5 {{ZBL|0874.20040}}
+
* Lothaire, M. ''Combinatorics on Words'' (2nd ed.) Encyclopedia of Mathematics and Its Applications '''17'''  Cambridge University Press (1997) ISBN 0-521-59924-5 {{ZBL|0874.20040}}
 
* Lothaire, M. ''Algebraic Combinatorics on Words'' Encyclopedia of Mathematics and Its Applications '''90''', Cambridge University Press (2011 [2002]) ISBN 978-0-521-18071-9 {{ZBL|1221.68183}}
 
* Lothaire, M. ''Algebraic Combinatorics on Words'' Encyclopedia of Mathematics and Its Applications '''90''', Cambridge University Press (2011 [2002]) ISBN 978-0-521-18071-9 {{ZBL|1221.68183}}
 
* Pytheas Fogg, N. (ed.) ''Substitutions in dynamics, arithmetics and combinatorics'' Lecture Notes in Mathematics '''1794''' Springer (2002) ISBN 978-3-540-44141-0 {{ZBL|1014.11015}}
 
* Pytheas Fogg, N. (ed.) ''Substitutions in dynamics, arithmetics and combinatorics'' Lecture Notes in Mathematics '''1794''' Springer (2002) ISBN 978-3-540-44141-0 {{ZBL|1014.11015}}
  
 
{{TEX|done}}
 
{{TEX|done}}

Revision as of 21:47, 23 March 2018

An infinite sequence of symbols over a binary alphabet defined by a recursion related to that of the Fibonacci numbers.

Let $A$ be the alphabet $\{a,b\}$ and define a sequence of finite words $f_n$, $n \ge 1$ by $f_1 = a$, $f_2 = ab$ and $f_{n+1} = f_n \cdot f_{n-1}$ where $\cdot$ denotes concatenation. The Fibonacci word $\mathcal{F}$ is defined as $$ \mathcal{F} = f_1 \cdot f_2 \cdot \cdots \cdot f_n \cdot \cdots $$ and, since $f_n$ is an initial factor of $f_{n+1}$ we may also obtain $\mathcal{F}$ as the limit of the $f_n$. We have $$ \mathcal{F} = a ab aab abaab aababaab abaabaababaab \ldots \ . $$

The Fibonacci word has complexity function $c_{\mathcal{F}}(n) = n+1$ and hence is a Sturmian sequence. It is a morphic word, a fixed point of the endomorphism $a \mapsto ab$, $b \mapsto a$.

References

  • Allouche, Jean-Paul; Shallit, Jeffrey Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press (2003) ISBN 978-0-521-82332-6 Zbl 1086.11015
  • Lothaire, M. Combinatorics on Words (2nd ed.) Encyclopedia of Mathematics and Its Applications 17 Cambridge University Press (1997) ISBN 0-521-59924-5 Zbl 0874.20040
  • Lothaire, M. Algebraic Combinatorics on Words Encyclopedia of Mathematics and Its Applications 90, Cambridge University Press (2011 [2002]) ISBN 978-0-521-18071-9 Zbl 1221.68183
  • Pytheas Fogg, N. (ed.) Substitutions in dynamics, arithmetics and combinatorics Lecture Notes in Mathematics 1794 Springer (2002) ISBN 978-3-540-44141-0 Zbl 1014.11015
How to Cite This Entry:
Fibonacci word. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fibonacci_word&oldid=43011