cp's OEIS Frontend

A051041 Number of squarefree quaternary words of length n.

%I A051041 #37 Feb 16 2025 08:32:41
%S A051041 1,4,12,36,96,264,696,1848,4848,12768,33480,87936,230520,604608,
%T A051041 1585128,4156392,10895952,28566216,74887056,196322976,514662960,
%U A051041 1349208600,3536962584,9272217936,24307198464,63721617888,167046745992,437914664688,1147996820376,3009483583056,7889385389784,20682088837608,54218261608896
%N A051041 Number of squarefree quaternary words of length n.
%C A051041 a(n), n > 0, is a multiple of 4 by symmetry. - _Michael S. Branicky_, Jun 20 2022
%H A051041 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 A051041 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 A051041 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SquarefreeWord.html">Squarefree Word.</a>
%F A051041 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 A051041 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 A051041 G.f. = 1 + 4*x + 12*x^2 + 36*x^3 + 96*x^4 + 264*x^5 + 696*x^6 + 1848*x^7 + ....
%o A051041 (Python)
%o A051041 def isf(s): # incrementally squarefree (check factors ending in last letter)
%o A051041     for l in range(1, len(s)//2 + 1):
%o A051041         if s[-2*l:-l] == s[-l:]: return False
%o A051041     return True
%o A051041 def aupton(nn, verbose=False):
%o A051041     alst, sfs = [1], set("1")
%o A051041     for n in range(1, nn+1):
%o A051041         an = 4*len(sfs)
%o A051041         sfsnew = set(s+i for s in sfs for i in "0123" if isf(s+i))
%o A051041         alst, sfs = alst+[an], sfsnew
%o A051041         if verbose: print(n, an)
%o A051041     return alst
%o A051041 print(aupton(14)) # _Michael S. Branicky_, Jun 20 2022
%Y A051041 Cf. A006156.
%Y A051041 Third column of A215075, multiplied by 24 (except for the first three terms). - _Arseny Shur_, Apr 26 2015
%K A051041 nonn
%O A051041 0,2
%A A051041 _Eric W. Weisstein_
%E A051041 More terms from _David Wasserman_, Feb 27 2002
%E A051041 a(13)-a(15) from _John W. Layman_, Mar 03 2004
%E A051041 a(16)-a(25) from _Max Alekseyev_, Jul 03 2006
%E A051041 a(26)-a(30) from _Giovanni Resta_, Mar 20 2020