A "square" word consists of two identical adjacent subwords (for example, acbacb). A squarefree word contains no square words as subwords (for
example, abcacbabcb). The only squarefree binary words are , ,
ab, ba, aba, and bab (since aa, bb, aaa,
aab, abb, baa, bba, and bbb contain square identical
adjacent subwords a, b, a, a, b, a, b,
and b, respectively).
However, there are arbitrarily long ternary squarefree words. The number of ternary squarefree words of length , 2, ... are 1, 3, 6, 12, 18, 30, 42, 60, ... (OEIS A006156),
and
is bounded by
(Brandenburg 1983). In addition,
(Brinkhuis 1983, Noonan and Zeilberger 1999).
The number of squarefree quaternary words of length , 2, ... are 4, 12, 36, 96, 264, 696, ... (OEIS A051041).
Allouche, J.-P. and Shallit, J. "Repetition in Words." §1.6 in Automatic
Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge
University Press, pp. 14-16, 2003.Baake, M.; Elser, V.; and Grimm,
U. "The Entropy of Square-Free Words." 8 Sep 1998. http://arxiv.org/abs/math-ph/9809010.Bean,
D. R.; Ehrenfeucht, A.; and McNulty, G. F. "Avoidable Patterns in
Strings of Symbols." Pacific J. Math.85, 261-294, 1979.Berstel,
J. and Reutenauer, C. "Square-Free Words and Idempotent Semigroups." In
Combinatorics
on Words (Ed. M. Lothaire). Reading, MA: Addison-Wesley, pp. 18-38,
1983.Brandenburg, F.-J. "Uniformly Growing th Power-Free Homomorphisms." Theor. Comput. Sci.23,
69-82, 1983.Brinkhuis, J. "Non-Repetitive Sequences on Three Symbols."
Quart. J. Math. Oxford Ser. 234, 145-149, 1983.Crochemore,
M. "Sharp Characterizations of Squarefree Morphisms." Theor. Comput.
Sic.18, 221-226, 1982.Crochemore, M. "Tests sur les
morphismes faiblement sans carré." In Combinatorics
on Words (Ed. L. J. Cummings). Toronto: Academic Press, pp. 63-89,
1983.Finch, S. R. "Pattern-Free Word Constants." §5.17
in Mathematical
Constants. Cambridge, England: Cambridge University Press, pp. 367-371,
2003.Kobayashi, Y. "Repetition-Free Words." Theor. Comput.
Sci.44, 175-197, 1986.Leconte, M. "th Power-Free Codes." In Automata
on Infinite Words (Ed. M. Nivat and D. Perrin). Berlin: Springer-Verlag,
pp. 172-178, 1985.Noonan, J. and Zeilberger, D. "The Goulden-Jackson
Cluster Method: Extensions, Applications, and Implementations." J. Differ.
Eq. Appl.5, 355-377, 1999.Pleasants, P. A. B.
"Nonrepetitive Sequences." Proc. Cambridge Philos. Soc.68,
267-274, 1970.Restivo, A. and Salemi, S. "Overlap-Free Words on
Two Symbols." In Automata
on Infinite Words (Ed. M. Nivat and D. Perrin). New York: Springer-Verlag,
pp. 198-206, 1985.Sloane, N. J. A. Sequences A006156/M2550
and A051041 in "The On-Line Encyclopedia
of Integer Sequences."Thue, A. "Über unendliche Zeichenreihen."
Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana7, 1-22, 1906.
Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; and Thalberg, K. (Eds.). Selected
Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget, pp. 139-158,
1977.Thue, A. "Über die gegenseitige Lage gleicher Teile gewisser
Zeichenreihen." Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana1,
1-67, 1912. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; and Thalberg, K. (Eds.).
Selected Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget,
pp. 413-477, 1977.
, 
,
ab, ba, aba, and bab (since aa, bb, aaa,
aab, abb, baa, bba, and bbb contain square identical
adjacent subwords a, b, a, a, b, a, b,
and b, respectively).
of ternary squarefree words of length 
, 2, ... are 1, 3, 6, 12, 18, 30, 42, 60, ... (OEIS A006156),
and 
is bounded by
![S=lim_(n->infty)[s(n)]^(1/n)=1.302...](/images/equations/SquarefreeWord/NumberedEquation2.svg)
, 2, ... are 4, 12, 36, 96, 264, 696, ... (OEIS A051041).
th Power-Free Homomorphisms." Theor. Comput. Sci. 23,
69-82, 1983.Brinkhuis, J. "Non-Repetitive Sequences on Three Symbols."
Quart. J. Math. Oxford Ser. 2 34, 145-149, 1983.Crochemore,
M. "Sharp Characterizations of Squarefree Morphisms." Theor. Comput.
Sic. 18, 221-226, 1982.Crochemore, M. "Tests sur les
morphismes faiblement sans carré." In 
th Power-Free Codes." In