|
%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
|
