cp's OEIS Frontend

A213975 List of subwords of A003842 arranged in lexicographic order.

%I A213975 #66 Aug 06 2024 10:36:17
%S A213975 1,2,11,12,21,112,121,211,212,1121,1211,1212,2112,2121,11211,11212,
%T A213975 12112,12121,21121,21211,112112,112121,121121,121211,211211,211212,
%U A213975 212112,1121121,1121211,1211211,1211212,1212112,2112112,2112121,2121121,11211212,11212112
%N A213975 List of subwords of A003842 arranged in lexicographic order.
%C A213975 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.
%C A213975 For another version of this sequence see the Noe link at A003849 (and included below).
%H A213975 Alois P. Heinz, <a href="/A213975/b213975.txt">Table of n, a(n) for n = 1..10010</a>
%H A213975 Wai-Fong Chuan and Hui-Ling Ho, <a href="https://doi.org/10.1016/j.tcs.2005.08.033">Locating factors of the infinite Fibonacci word</a>, Theoret. Comput. Sci. 349 (2005), no. 3, 429--442. MR2183167 (2007c:68115)
%H A213975 James D. Currie and Kalle Saari, <a href="http://www.numdam.org/item/ITA_2009__43_1_165_0/">Least Periods of Factors of Infinite Words</a>, RAIRO - Theoretical Informatics and Applications, January 2009, 43, pp. 165-178.
%H A213975 M. Lothaire, <a href="http://www-igm.univ-mlv.fr/~berstel/Lothaire/">Algebraic Combinatorics on Words</a>, Cambridge, 2002; see Chap. 2.
%H A213975 F. Mignosi, A. Restivo, M. Sciortino, <a href="http://dx.doi.org/10.1016/S0304-3975(00)00436-9">Words and forbidden factors</a>, WORDS (Rouen, 1999). Theoret. Comput. Sci. 273 (2002), no. 1-2, 99--117. MR1872445 (2002m:68096).
%H A213975 T. D. Noe, <a href="/A003849/a003849.txt">The first 1652 subwords of A003849, including leading zeros.</a>
%H A213975 Kalle Saari, <a href="https://citeseerx.ist.psu.edu/pdf/226ad5ee4e916bbddb5775d36d4d126074ca1c27">Periods of factors of the Fibonacci word</a>, Department of Mathematics and Turku Centre for Computer Science, University of Turku, 2001 4 Turku, Finland.
%H A213975 Kalle Saari, <a href="https://www.semanticscholar.org/paper/PERIODS-OF-FACTORS-OF-THE-FIBONACCI-WORD-KALLE-Saari/226ad5ee4e916bbddb5775d36d4d126074ca1c27">Periods of factors of the Fibonacci word</a>, in Proceedings of the Sixth International Conference on Words (WORDS’07). Institut de Mathématiques de Luminy (2007) 273-279.
%H A213975 Zhi-Xiong Wen and Zhi-Ying Wen, <a href="https://doi.org/10.1006/eujc.1994.1060">Some properties of the singular words of the Fibonacci word</a>, European J. Combin. 15 (1994), 587-598.
%F A213975 The list S(n), say, of words of length n in this sequence can be constructed recursively as follows.
%F A213975 There are two words of length 1, namely S(1)={1,2}.
%F A213975 The n+2 words in S(n+1) are obtained from the n+1 words in S(n) thus:
%F A213975 if u in S(n) is the reverse of a prefix of the Fibonacci word A003842 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.
%F A213975 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).
%F A213975 On the other hand, consider for example u=21121 in S(5), which is the reverse of the first 5 digits of A003842. Now both u1 and u2 are in S(6).
%e A213975 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.
%p A213975 S:= proc(n) option remember;
%p A213975       `if`(n<2, [2-n], [S(n-1)[], S(n-2)[]])
%p A213975     end:
%p A213975 T:= proc(n) local k, l, m, s;
%p A213975       for k while nops(S(k))<n do od;
%p A213975       do l:= S(k); m:= nops(l);
%p A213975          s:= {seq(parse(cat(l[i..i+n-1][])), i=1..m-n+1)};
%p A213975          if nops(s) = n+1 then break else k:= k+1 fi
%p A213975       od; sort([s[]])[]
%p A213975     end:
%p A213975 seq(T(n), n=1..10);  # _Alois P. Heinz_, Jul 04 2012
%t A213975 nmax = 10;
%t A213975 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);
%t A213975 seq[s = 1];
%t A213975 While[seq[s] != seq[s-1], s++];
%t A213975 seq[s] (* _Jean-François Alcover_, Apr 28 2020 *)
%Y A213975 Cf. A003842, A214207, A214208, A214209, A214216, A214217.
%K A213975 nonn
%O A213975 1,2
%A A213975 _N. J. A. Sloane_, Jul 03 2012, Jul 10 2012