|
| |
|
|
A006156
|
|
Number of ternary squarefree words of length n.
(Formerly M2550)
|
|
11
|
|
|
|
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 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
|
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
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
|
|
|
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 (* 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, _Jeffrey Shallit_, Doron Zeilberger
|
|
|
EXTENSIONS
|
Links corrected by Eric Rowland, Sep 16 2010
|
|
|
STATUS
|
approved
|
| |
|
|
