A282212 - OEIS

%I #25 Apr 06 2023 10:27:00

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

%T 444,528,690,966,1236,1602,2112,2712,3522,4818,6150,8094,10452,13854,

%U 17784,23082,29970,39438,51030,66792,86502,113064,147036,191952,249390

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

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

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

%C The structure of such words was described by Li (1976). - _Jeffrey Shallit_, Jan 16 2019

%C a(n) is a multiple of 3 by symmetry. - _Michael S. Branicky_, Jul 21 2021

%H Michael S. Branicky, <a href="/A282212/b282212.txt">Table of n, a(n) for n = 1..62</a>

%H Shuo-Yen R. Li, <a href="https://doi.org/10.1002/sapm197655183">Annihilators in nonrepetitive semigroups</a>, Studies in Applied Math. 55 (1976), 83-85.

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

%p extend:= proc(w) local res,t,wt,i;

%p   res:= NULL;

%p   for t from "0" to "2" do

%p     wt:= cat(w,t);

%p     if andmap(i -> wt[-2*i..-i-1] <> wt[-i..-1], [$1..floor(length(wt)/2)]) then res:= wt,res fi

%p   od:

%p res

%p end proc:

%p L[1]:= ["0"]:

%p for n from 1 to 43 do

%p   A[n]:= 0: L[n+1]:= NULL;

%p   for t in L[n] do

%p     r:= extend(t);

%p     if [r] = [] then A[n]:= A[n]+3

%p     else L[n+1]:= L[n+1],r

%p     fi

%p   od;

%p   L[n+1]:= [L[n+1]];

%p od:

%p seq(A[n],n=1..43); # _Robert Israel_, Feb 09 2017

%o (Python)

%o def isf(s): # incrementally squarefree

%o     for l in range(1, len(s)//2 + 1):

%o         if s[-2*l:-l] == s[-l:]: return False

%o     return True

%o def aupton(nn, verbose=False):

%o     alst, sfs = [], set("0")

%o     for n in range(1, nn+1):

%o         an, sfsnew = 0, set()

%o         for s in sfs:

%o             se = [s+i for i in "012" if isf(s+i)]

%o             if len(se) > 0: sfsnew.update(se)

%o             else: an += 3

%o         alst, sfs = alst+[an], sfsnew

%o         if verbose: print(n, an)

%o     return alst

%o print(aupton(40)) # _Michael S. Branicky_, Jul 21 2021

%Y Cf. A006156.

%K nonn

%O 1,7

%A _Jeffrey Shallit_, Feb 09 2017

%E a(37)-a(43) from _Robert Israel_, Feb 09 2017

%E a(44) and beyond from _Michael S. Branicky_, Jul 21 2021