login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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).]

M. Baake, V. Elser and U. Grimm, The entropy of square-free words, arXiv:math-ph/9809010, 1998.

F.-J. Brandenburg, Uniformly growing k-th power-free homomorphisms, Theoretical Computer Sci., 23 (1983), 69-82.

J. Brinkhuis, Non-repetitive sequences on three symbols, Quart. J. Math. Oxford, 34 (1983), 145-149.

S. Ekhad and D. Zeilberger, There are more than 2^(n/17) n-letter ternary square-free words, J. Integer Sequences, Vol. 1 (1998), Article 98.1.9

U. Grimm, Improved bounds on the number of ternary square-free words, J. Integer Sequences, Vol. 4 (2001), Article 01.2.7

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.

Mari Huova and Juhani Karhumäki, On Unavoidability of k-abelian Squares in Pure Morphic Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.9

R. Kolpakov, Efficient Lower Bounds on the Number of Repetition-free Words, J. Integer Sequences, Vol. 10 (2007), Article 07.3.2.

J. Noonan and D. Zeilberger, The Goulden-Jackson cluster method: extensions, applications and implementations, arXiv:math/9806036 [math.CO], 1998.

C. Richard and U. Grimm, On the entropy and letter frequencies of ternary square-free words, arXiv:math/0302302 [math.CO], 2003.

A. M. Shur, Growth properties of power-free languages, Computer Science Review, Vol. 6 (2012), 187-208.

A. M. Shur, Numerical values of the growth rates of power-free languages</a, arXiv:1009.4415 [cs.FL], 2010.

Yuriy Tarannikov, The minimal density of a letter in an infinite ternary square-free 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

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

CROSSREFS

Cf. A060688.

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

Sequence in context: A180005 A116958 A242477 * A171370 A061776 A074899

Adjacent sequences:  A006153 A006154 A006155 * A006157 A006158 A006159

KEYWORD

nonn,nice,changed

AUTHOR

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

EXTENSIONS

Links corrected by Eric Rowland, Sep 16 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified April 27 06:38 EDT 2015. Contains 257086 sequences.