The Fibonacci word starts from $0$ subject to the rules $0 \mapsto 1, 1 \mapsto 01$ (or some variant thereof). The come from cutting sequences of the torus of a line of golden ratio slope. It is a 1D version of the Penrose Tiling.
...1010110101101101011010110110101101101011010110110101101...
http://upload.wikimedia.org/wikipedia/commons/2/2d/Fibonacci_word_cutting_sequence.png
The Fibonacci word is has minimal complexity above a periodic word -- there are n+1 subwords of length n, making it a Sturmian word.
- 5 subwords of length 4: "0101", "0110", "1010", "1011", "1101"
- 8 subwords of length 7: "0101101", "0110101", "0110110", "1010110", "1011010", "1011011", "1101011", "1101101"
As an experiment, I sorted the subwords of length n alphabetically The words are arranged in an infinite tree, where each word is descendant of its subword.
As a shorthand, I only placed the last letter of each word on each diagonal. Edges represent inclusion... drawn so any path from the top left corner "." appears in the Fibonacci word. Each Fibonacci subword corresponds to a path.
What is the structure of this tree? Is there any regularity to the location of the branches?
The complement of the tree becomes a tesselation of the Euclidean plane by "thin $\infty$-ominos", which is amusing.
.-1-1-0-1-1-0-1-0-1-1-0
| | |
0 0-1-1 0-1-1-0-1-1-0
| | | |
1-1 0 0-1-1-0-1 0-1
| | | | |
0 0 1-1 0-1-1 0-1
| | | |
1 1-1 0-1-1 0-1
| | | |
1 0 0-1-1 0-1
| | | |
0 1-1 0 1-1
| | |
1-1 0 1-1
| | |
0 0 1-1
| | |
1 1 0
| |
1 0
|
0