%I #36 Jun 21 2022 05:07:04
%S 1,4,12,36,96,264,696,1848,4848,12768,33480,87936,230520,604608,
%T 1585128,4156392,10895952,28566216,74887056,196322976,514662960,
%U 1349208600,3536962584,9272217936,24307198464,63721617888,167046745992,437914664688,1147996820376,3009483583056,7889385389784,20682088837608,54218261608896
%N Number of squarefree quaternary words of length n.
%C a(n), n > 0, is a multiple of 4 by symmetry. - _Michael S. Branicky_, Jun 20 2022
%H A. M. Shur, <a href="http://dx.doi.org/10.1016/j.cosrev.2012.09.001">Growth properties of power-free languages</a>, Computer Science Review, Vol. 6 (2012), 187-208.
%H A. M. Shur, <a href="http://arxiv.org/abs/1009.4415">Numerical values of the growth rates of power-free languages</a>, arXiv:1009.4415 [cs.FL], 2010.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SquarefreeWord.html">Squarefree Word.</a>
%F Let L be the limit lim a(n)^{1/n}, which exists because a(n) is a submultiplicative sequence. Then L=2.6215080... (Shur 2010). See (Shur 2012) for the methods of estimating such limits. - _Arseny Shur_, Apr 26 2015
%e There are 96 quaternary squarefree words of length 4: each of the words 0102, 0120, 0121, 0123 has 4!=24 images under the permutations of the set {0,1,2,3}. - _Arseny Shur_, Apr 26 2015
%e G.f. = 1 + 4*x + 12*x^2 + 36*x^3 + 96*x^4 + 264*x^5 + 696*x^6 + 1848*x^7 + ....
%o (Python)
%o def isf(s): # incrementally squarefree (check factors ending in last letter)
%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 = [1], set("1")
%o for n in range(1, nn+1):
%o an = 4*len(sfs)
%o sfsnew = set(s+i for s in sfs for i in "0123" if isf(s+i))
%o alst, sfs = alst+[an], sfsnew
%o if verbose: print(n, an)
%o return alst
%o print(aupton(14)) # _Michael S. Branicky_, Jun 20 2022
%Y Cf. A006156.
%Y Third column of A215075, multiplied by 24 (except for the first three terms). - _Arseny Shur_, Apr 26 2015
%K nonn
%O 0,2
%A _Eric W. Weisstein_
%E More terms from _David Wasserman_, Feb 27 2002
%E a(13)-a(15) from _John W. Layman_, Mar 03 2004
%E a(16)-a(25) from _Max Alekseyev_, Jul 03 2006
%E a(26)-a(30) from _Giovanni Resta_, Mar 20 2020