|
%I M2550 #98 Jan 14 2022 23:54:25
%S 1,3,6,12,18,30,42,60,78,108,144,204,264,342,456,618,798,1044,1392,
%T 1830,2388,3180,4146,5418,7032,9198,11892,15486,20220,26424,34422,
%U 44862,58446,76122,99276,129516,168546,219516,285750,372204,484446,630666,821154
%N Number of ternary squarefree words of length n.
%C a(n), n > 0, is a multiple of 3 by symmetry. - _Michael S. Branicky_, Jul 21 2021
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Hans Havermann, <a href="/A006156/b006156.txt">Table of n, a(n) for n = 0..110</a> [Terms 1-90 come from The Entropy of Square-Free Words by Baake, Elser, & Grimm (pages 10, 11). Terms 91-110 come from Grimm's Improved Bounds on the Number of Ternary Square-Free Words (page 3).]
%H M. Baake, V. Elser and U. Grimm, <a href="http://arxiv.org/abs/math-ph/9809010">The entropy of square-free words</a>, arXiv:math-ph/9809010, 1998.
%H Jean Berstel, <a href="http://www-igm.univ-mlv.fr/~berstel/Articles/1984Stacs.pdf">Some recent results on squarefree words</a>, STACS 84, Symposium of Theoretical Aspects of Computer Science Paris, 11-13, 1984, pp 14-25.
%H F.-J. Brandenburg, <a href="http://dx.doi.org/10.1016/0304-3975(88)90009-6">Uniformly growing k-th power-free homomorphisms</a>, Theoretical Computer Sci., 23 (1983), 69-82.
%H J. Brinkhuis, <a href="https://doi.org/10.1093/qmath/34.2.145">Non-repetitive sequences on three symbols</a>, Quart. J. Math. Oxford, 34 (1983), 145-149.
%H S. Ekhad and D. Zeilberger, <a href="http://www.cs.uwaterloo.ca/journals/JIS/zeil.html">There are more than 2^(n/17) n-letter ternary square-free words</a>, J. Integer Sequences, Vol. 1 (1998), Article 98.1.9.
%H U. Grimm, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/GRIMM/words.html">Improved bounds on the number of ternary square-free words</a>, J. Integer Sequences, Vol. 4 (2001), Article 01.2.7.
%H Mari Huova, <a href="http://www.doria.fi/bitstream/handle/10024/95677/TUCSDissertation172.pdf">Combinatorics on Words. New Aspects on Avoidability, Defect Effect, Equations and Palindromes</a>, Turku Centre for Computer Science, TUCS Dissertations No 172, April 2014.
%H Mari Huova and Juhani Karhumäki, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Huova/huova2.html">On Unavoidability of k-abelian Squares in Pure Morphic Words</a>, Journal of Integer Sequences, Vol. 16 (2013), #13.2.9.
%H R. Kolpakov, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Kolpakov/kolpakov42.html">Efficient Lower Bounds on the Number of Repetition-free Words</a>, J. Integer Sequences, Vol. 10 (2007), Article 07.3.2.
%H Vladislav Makarov, <a href="https://arxiv.org/abs/2012.03926">Counting ternary square-free words quickly</a>, arXiv:2012.03926 [cs.FL], 2020.
%H J. Noonan and D. Zeilberger, <a href="http://arXiv.org/abs/math.CO/9806036">The Goulden-Jackson cluster method: extensions, applications and implementations</a>, arXiv:math/9806036 [math.CO], 1998.
%H C. Richard and U. Grimm, <a href="http://arXiv.org/abs/math.CO/0302302">On the entropy and letter frequencies of ternary square-free words</a>, arXiv:math/0302302 [math.CO], 2003.
%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 Yuriy Tarannikov, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Tarannikov/tarann7.html">The minimal density of a letter in an infinite ternary square-free word is 0.2746...</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.2.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SquarefreeWord.html">Squarefree Word</a>
%F a(n) >= 2^(n/17), see Zeilberger. Let L = lim_{n->infinity} a(n)^(1/n); then L exists and Grimm proves 1.109999 < L < 1.317278. - _Charles R Greathouse IV_, Nov 29 2013
%F L exists since a(n) is submultiplicative; 1.3017597 < L < 1.3017619 (Shur 2012); the gap between the bounds can be made less than any given constant. - _Arseny Shur_, Apr 22 2015
%e Let the alphabet be {a,b,c}. Then:
%e a(1)=3: a, b, c.
%e a(2)=6: all xy except aa, bb, cc.
%e a(3)=12: aba, abc, aca, acb and similar words beginning with b and c, for a total of 12.
%t (* A simple solution (though not at all efficient beyond n = 12) : *) a[0] = 1; a[n_] := a[n] = Length @ DeleteCases[Tuples[Range[3], n] , {a___, b__, b__, c___} ]; s = {}; Do[Print["a[", n, "] = ", a[n]]; AppendTo[s, a[n]], {n, 0, 12}]; s (* _Jean-François Alcover_, May 02 2011 *)
%t Length/@NestList[DeleteCases[Flatten[Outer[Append, #, Range@3, 1], 1], {___, x__, x__, ___}] &, {{}}, 20] (* _Vladimir Reshetnikov_, May 16 2016 *)
%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("0")
%o for n in range(1, nn+1):
%o an = 3*len(sfs)
%o sfsnew = set(s+i for s in sfs for i in "012" if isf(s+i))
%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. A060688, A282212.
%Y Second column of A215075, multiplied by 3!=6.
%K nonn,nice
%O 0,2
%A _N. J. A. Sloane_, _Jeffrey Shallit_, _Doron Zeilberger_
%E Links corrected by _Eric Rowland_, Sep 16 2010
|
