

A006156


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


12



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


REFERENCES

F.J. Brandenburg, Uniformly growing kth powerfree homomorphisms, Theoretical Computer Sci., 23 (1983), 6982.
J. Brinkhuis, Nonrepetitive sequences on three symbols, Quart. J. Math. Oxford, 34 (1983), 145149.
Mari Huova, Combinatorics on Words. New Aspects on Avoidability, Defect Effect, Equations and Palindromes, Turku Centre for Computer Science, TUCS Dissertations No 172, April 2014; http://www.doria.fi/bitstream/handle/10024/95677/TUCSDissertation172.pdf?sequence=4
John Noonan and Doron Zeilberger, The GouldenJackson Cluster Method: Extensions, Applications and Implementations, 1997.
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).]
M. Baake, V. Elser and U. Grimm, The entropy of squarefree words
S. Ekhad and D. Zeilberger, There are more than 2^(n/17) nletter ternary squarefree words, J. Integer Sequences, Vol. 1 (1998), Article 98.1.9
U. Grimm, Improved bounds on the number of ternary squarefree words, J. Integer Sequences, Vol. 4 (2001), Article 01.2.7
J. Noonan and D. Zeilberger, The GouldenJackson cluster method: extensions, applications and implementations
C. Richard and U. Grimm, On the entropy and letter frequencies of ternary squarefree words
Yuriy Tarannikov, The minimal density of a letter in an infinite ternary squarefree word is 0.2746..., Journal of Integer Sequences, Vol. 5 (2002), Article 02.2.2
Eric Weisstein's World of Mathematics, Squarefree Word


FORMULA

a(n) >= 2^(n/17), see Zeilberger. Let L = lim a(n)^(1/n); then L exists and Grimm proves 1.109999 < L < 1.317278.  Charles R Greathouse IV, Nov 29 2013


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


CROSSREFS

Cf. A060688.
Sequence in context: A180005 A116958 A242477 * A171370 A061776 A074899
Adjacent sequences: A006153 A006154 A006155 * A006157 A006158 A006159


KEYWORD

nonn,nice


AUTHOR

N. J. A. Sloane, Jeffrey Shallit, Doron Zeilberger


EXTENSIONS

Links corrected by Eric Rowland, Sep 16 2010


STATUS

approved



