login
List of minimal forbidden subwords of the Fibonacci word A003482.
2

%I #17 Apr 28 2020 09:21:50

%S 22,111,21212,11211211,2121121211212,112112121121121211211,

%T 2121121211211212112121121121211212,

%U 1121121211211212112121121121211211212112121121121211211,21211212112112121121211211212112112121121211211212112121121121211211212112121121121211212

%N List of minimal forbidden subwords of the Fibonacci word A003482.

%C If S is one of the terms of this sequence, then no word RS can appear as a subword of A003482.

%C Or, make a list of all words in {1,2}* that do not appear as factors of A003482 and discard any word which has a shorter word on the list as a right factor.

%C All the terms are palindromes.

%C Complementing the first and last digits of each term gives (essentially) A214217.

%H A. de Luca, <a href="http://mathoverflow.net/questions/60514/subwords-of-the-fibonacci-word">Subwords of the Fibonacci word</a>, MathOverflow, April 9, 2011.

%H 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).

%F To get a(n), take A106750(n+2), delete last two digits, producing a palindrome P, say. Then a(n) = 1P1 if n is odd, or 2P2 if n is even.

%e A106750(3)=121 -> P=1 -> 111 = a(1).

%e A106750(4)=12112 -> P=121 -> 2121 = a(2).

%e A106750(5)=12112121 -> P=121121 -> 11211211 = a(3).

%Y Cf. A003842, A106750, A213975, A214217.

%K nonn

%O 1,1

%A _N. J. A. Sloane_, Jul 10 2012