

A006156


Number of ternary squarefree words of length n.
(Formerly M2550)


18



1, 3, 6, 12, 18, 30, 42, 60, 78, 108, 144, 204, 264, 342, 456, 618, 798, 1044, 1392, 1830, 2388, 3180, 4146, 5418, 7032, 9198, 11892, 15486, 20220, 26424, 34422, 44862, 58446, 76122, 99276, 129516, 168546, 219516, 285750, 372204, 484446, 630666, 821154
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS



REFERENCES

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


LINKS

Hans Havermann, Table of n, a(n) for n = 0..110 [Terms 190 come from The Entropy of SquareFree Words by Baake, Elser, & Grimm (pages 10, 11). Terms 91110 come from Grimm's Improved Bounds on the Number of Ternary SquareFree Words (page 3).]


FORMULA

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
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


EXAMPLE

Let the alphabet be {a,b,c}. Then:
a(1)=3: a, b, c.
a(2)=6: all xy except aa, bb, cc.
a(3)=12: aba, abc, aca, acb and similar words beginning with b and c, for a total of 12.


MATHEMATICA

(* 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 (* JeanFrançois Alcover, May 02 2011 *)
Length/@NestList[DeleteCases[Flatten[Outer[Append, #, Range@3, 1], 1], {___, x__, x__, ___}] &, {{}}, 20] (* Vladimir Reshetnikov, May 16 2016 *)


PROG

(Python)
def isf(s): # incrementally squarefree (check factors ending in last letter)
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 = [1], set("0")
for n in range(1, nn+1):
an = 3*len(sfs)
sfsnew = set(s+i for s in sfs for i in "012" if isf(s+i))
alst, sfs = alst+[an], sfsnew
if verbose: print(n, an)
return alst


CROSSREFS

Second column of A215075, multiplied by 3!=6.


KEYWORD

nonn,nice


AUTHOR



EXTENSIONS



STATUS

approved



