|
|
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 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).]
|
|
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 (* Jean-Franç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
|
|
|
|