A330257 - OEIS

%I #13 Dec 10 2019 20:03:10

%S 1,3,6,10,14,20,24,30,36,44,48,60,60,62,72,82,88,96,112,120,120,136,

%T 148,164,152,154,148,162,176,190,196,210,216,224,228,248,272,284,296,

%U 300,296,320,332,356,356,376,400,416,380,382,376,382,356,374,392,410

%N Number of length-n ternary squarefree words having no occurrences of either 010 or 212.

%C An example of such a word is A036577.

%D A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), 1-67. Reprinted in Selected Mathematical Papers of Axel Thue, T. Nagell, editor, Universitetsforlaget, Oslo, 1977, pp. 413-478.

%H Robert Israel, <a href="/A330257/b330257.txt">Table of n, a(n) for n = 0..1000</a>

%H J. Berstel, <a href="http://www-igm.univ-mlv.fr/~berstel/Articles/1994ThueTranslation.pdf">Axel Thue's papers on repetitions in words: a translation</a>, Publications du Laboratoire de Combinatoire et d'Informatique Mathématique, Vol. 20, Université du Québec à Montréal, February 1995.

%p filter:= proc(s) local n,j,cands;

%p   n:= length(s);

%p   if n >= 3 and (s[1..3] = "010" or s[1..3]="212") then return false fi;

%p   for j from 1 to min(n/2, 5) do

%p     if s[1..j] = s[j+1..2*j] then return false fi;

%p   od;

%p   if n >= 12 then

%p     cands:= select(j -> j > 1 and j <= ceil((1+n)/2), {StringTools:-SearchAll(s[1..6],s)});

%p     for j in cands do if s[1..j-1] = s[j..2*j-2] then return false fi       od;

%p   fi;

%p   true

%p end proc:

%p S[0]:= {""}:

%p for n from 1 to 100 do

%p   S[n]:= select(filter, map(t -> (cat("0",t),cat("1",t),cat("2",t)), S[n-1]));

%p od:

%p seq(nops(S[i]),i=0..100); # _Robert Israel_, Dec 10 2019

%Y Cf. A036577, A330258, A330259.

%K nonn,look

%O 0,2

%A _Jeffrey Shallit_, Dec 07 2019