A282212 Number of maximal squarefree words of length n over the alphabet {0,1,2}.

0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 6, 6, 6, 24, 24, 24, 36, 54, 54, 120, 138, 216, 240, 384, 444, 528, 690, 966, 1236, 1602, 2112, 2712, 3522, 4818, 6150, 8094, 10452, 13854, 17784, 23082, 29970, 39438, 51030, 66792, 86502, 113064, 147036, 191952, 249390

Offset

1,7

Comments

A word is "squarefree" if it contains no nonempty block of the form xx.

A squarefree word w is maximal if wa contains a square for all symbols a.

The structure of such words was described by Li (1976). - Jeffrey Shallit, Jan 16 2019

a(n) is a multiple of 3 by symmetry. - Michael S. Branicky, Jul 21 2021

Links

Michael S. Branicky, Table of n, a(n) for n = 1..62

Shuo-Yen R. Li, Annihilators in nonrepetitive semigroups, Studies in Applied Math. 55 (1976), 83-85.

Example

For n = 7 the maximal squarefree words are 0102010 and the 5 others induced by permuting the symbols.

Maple

extend:= proc(w) local res, t, wt, i;
  res:= NULL;
  for t from "0" to "2" do
    wt:= cat(w, t);
    if andmap(i -> wt[-2*i..-i-1] <> wt[-i..-1], [$1..floor(length(wt)/2)]) then res:= wt, res fi
  od:
res
end proc:
L[1]:= ["0"]:
for n from 1 to 43 do
  A[n]:= 0: L[n+1]:= NULL;
  for t in L[n] do
    r:= extend(t);
    if [r] = [] then A[n]:= A[n]+3
    else L[n+1]:= L[n+1], r
    fi
  od;
  L[n+1]:= [L[n+1]];
od:
seq(A[n], n=1..43); # Robert Israel, Feb 09 2017

Prog

(Python)
def isf(s): # incrementally squarefree
    for l in range(1, len(s)//2 + 1):
        if s[-2*l:-l] == s[-l:]: return False
    return True
def aupton(nn, verbose=False):
    alst, sfs = [], set("0")
    for n in range(1, nn+1):
        an, sfsnew = 0, set()
        for s in sfs:
            se = [s+i for i in "012" if isf(s+i)]
            if len(se) > 0: sfsnew.update(se)
            else: an += 3
        alst, sfs = alst+[an], sfsnew
        if verbose: print(n, an)
    return alst
print(aupton(40)) # Michael S. Branicky, Jul 21 2021

Crossrefs

Cf. A006156.

Sequence in context: A260712 A173066 A173452 * A074591 A318877 A035321

Adjacent sequences: A282209 A282210 A282211 * A282213 A282214 A282215

Keyword

nonn

Author

Jeffrey Shallit, Feb 09 2017

Extensions

a(37)-a(43) from Robert Israel, Feb 09 2017

a(44) and beyond from Michael S. Branicky, Jul 21 2021

Status

approved