|
| |
|
|
A006156
|
|
Number of ternary squarefree words of length n.
(Formerly M2550)
|
|
9
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
REFERENCES
| 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.
John Noonan and Doron Zeilberger, The Goulden-Jackson 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
| M. Baake, V. Elser and U. Grimm, The entropy of square-free words
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
J. Noonan and D. Zeilberger, The Goulden-Jackson cluster method: extensions, applications and implementations
C. Richard and U. Grimm, On the entropy and letter frequencies of ternary square-free words
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
|
|
|
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 (* From Jean-François Alcover, May 02 2011 *)
|
|
|
CROSSREFS
| Cf. A060688.
Sequence in context: A181026 A180005 A116958 * A171370 A061776 A074899
Adjacent sequences: A006153 A006154 A006155 * A006157 A006158 A006159
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Jeffrey Shallit, zeilberg(AT)euclid.math.temple.edu (Doron Zeilberger)
|
|
|
EXTENSIONS
| Links corrected by Eric Rowland (erowland(AT)tulane.edu), Sep 16 2010
|
| |
|
|
