Squarefree Word
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,
![S=lim_(n->infty)[s(n)]^(1/n)=1.302...](/images/equations/SquarefreeWord/NumberedEquation2.gif) |
(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. https://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. 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 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. Christiana 7, 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. Christiana 1, 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.
Weisstein, Eric W. "Squarefree Word." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SquarefreeWord.html
Contact the MathWorld Team
7 {1, 0, -2, 1} - 4 {2, -1, 1, -1}