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

1, 3, 6, 10, 14, 20, 24, 30, 36, 44, 48, 60, 60, 62, 72, 82, 88, 96, 112, 120, 120, 136, 148, 164, 152, 154, 148, 162, 176, 190, 196, 210, 216, 224, 228, 248, 272, 284, 296, 300, 296, 320, 332, 356, 356, 376, 400, 416, 380, 382, 376, 382, 356, 374, 392, 410

Offset

0,2

Comments

An example of such a word is A036577.

References

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.

Links

Robert Israel, Table of n, a(n) for n = 0..1000

J. Berstel, Axel Thue's papers on repetitions in words: a translation, Publications du Laboratoire de Combinatoire et d'Informatique Mathématique, Vol. 20, Université du Québec à Montréal, February 1995.

Maple

filter:= proc(s) local n, j, cands;
  n:= length(s);
  if n >= 3 and (s[1..3] = "010" or s[1..3]="212") then return false fi;
  for j from 1 to min(n/2, 5) do
    if s[1..j] = s[j+1..2*j] then return false fi;
  od;
  if n >= 12 then
    cands:= select(j -> j > 1 and j <= ceil((1+n)/2), {StringTools:-SearchAll(s[1..6], s)});
    for j in cands do if s[1..j-1] = s[j..2*j-2] then return false fi       od;
  fi;
  true
end proc:
S[0]:= {""}:
for n from 1 to 100 do
  S[n]:= select(filter, map(t -> (cat("0", t), cat("1", t), cat("2", t)), S[n-1]));
od:
seq(nops(S[i]), i=0..100); # Robert Israel, Dec 10 2019

Crossrefs

Cf. A036577, A330258, A330259.

Sequence in context: A310071 A330259 A024928 * A079552 A334454 A236758

Adjacent sequences: A330254 A330255 A330256 * A330258 A330259 A330260

Keyword

nonn,look

Author

Jeffrey Shallit, Dec 07 2019

Status

approved