|
|
A213975
|
|
List of subwords of A003842 arranged in lexicographic order.
|
|
9
|
|
|
1, 2, 11, 12, 21, 112, 121, 211, 212, 1121, 1211, 1212, 2112, 2121, 11211, 11212, 12112, 12121, 21121, 21211, 112112, 112121, 121121, 121211, 211211, 211212, 212112, 1121121, 1121211, 1211211, 1211212, 1212112, 2112112, 2112121, 2121121, 11211212, 11212112
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The Fibonacci word A003842 is a Sturmian word, which means that there are exactly n+1 different factors (or subwords) of length n for all n.
For another version of this sequence see the Noe link at A003849 (and included below).
|
|
LINKS
|
F. Mignosi, A. Restivo, M. Sciortino, Words and forbidden factors, WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096).
|
|
FORMULA
|
The list S(n), say, of words of length n in this sequence can be constructed recursively as follows.
There are two words of length 1, namely S(1)={1,2}.
The n+2 words in S(n+1) are obtained from the n+1 words in S(n) thus:
if u in S(n) is the reverse of a prefix of the Fibonacci word A003482 then both u0 and u1 are in S(n+1), otherwise u in S(n) has a unique extension ux in S(n+1), where x is determined by the requirement that no right factor of ux is one of the forbidden words listed in A214216.
For example, A214216 contains both 22 and 111. So if u ends with 2 then (since 22 is forbidden), x=1 and u1 is in S(n+1), while if u ends with 11 then (since 111 is forbidden) x=2 and u2 is in S(n+1).
On the other hand, consider for example u=21121 in S(5), which is the reverse of the first 5 digits of A003482. Now both u1 and u2 are in S(6).
|
|
EXAMPLE
|
A003842 begins 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, ... and we can see factors 1, 2, 11, 12, 21, but not 22.
|
|
MAPLE
|
S:= proc(n) option remember;
`if`(n<2, [2-n], [S(n-1)[], S(n-2)[]])
end:
T:= proc(n) local k, l, m, s;
for k while nops(S(k))<n do od;
do l:= S(k); m:= nops(l);
s:= {seq(parse(cat(l[i..i+n-1][])), i=1..m-n+1)};
if nops(s) = n+1 then break else k:= k+1 fi
od; sort([s[]])[]
end:
|
|
MATHEMATICA
|
nmax = 10;
seq[steps_] := seq[steps] = (S = SubstitutionSystem[{1 -> {1, 2}, 2 -> {1}}, {1}, steps] // Last; T[n_] := FromDigits /@ Union[Partition[S, n, 1]]; Table[T[n], {n, 1, nmax}] // Flatten);
seq[s = 1];
While[seq[s] != seq[s-1], s++];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|