A squarefree word is a word containing no substring of the form ,
where
is a nonempty finite word. Such a repeated block is called
a square (for example, acbacb). For example, abcacbabcb is squarefree,
as is the empty word. The only nonempty squarefree binary
words are , ,
ab, ba, aba, and bab. Avoiding aa and bb
forces alternation, and every alternating word of length
four contains abab or baba.
There are arbitrarily long ternary squarefree words. The number
of ternary squarefree words of length over a fixed three-letter alphabet
is given for ,
1, 2, ... by 1, 3, 6, 12, 18, 30, 42, 60, ... (OEIS A006156).
The exponential growth rate exists and satisfies
The published numerical bounds imply
(Shur 2012, pp. 2-3).
The number of squarefree quaternary words of length , 2, ... are 4, 12, 36, 96, 264, 696,
... (OEIS A051041).
Avoiding abelian squares is a stronger condition than squarefreeness. An abelian square has two
halves with the same letter counts, but they need not be identical. An infinite word avoiding abelian squares
requires at least four letters (Salo et al. 2026).
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. 234, 145-149, 1983.Crochemore,
M. "Sharp Characterizations of Squarefree Morphisms." Theor. Comput.
Sci.18, 221-226, 1982.Crochemore, M. "Tests sur les
morphismes faiblement sans carré." In Combinatorics
on Words (Ed. L. J. Cummings). Toronto, Ontario, Canada: 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, Germany:
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.Salo, V.; Vukusic, I.; and Wilson, C. "Avoiding
Abelian Squares with Three Colours in the Continuous Setting." 20 Oct 2026.
https://arxiv.org/abs/2610.28376.Shur,
A. M. "Numerical Values of the Growth Rates of Power-Free Languages."
4 Apr 2012. https://arxiv.org/abs/1009.4415v2.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.
,
where 
is a nonempty finite word. Such a repeated block is called
a square (for example, acbacb). For example, abcacbabcb is squarefree,
as is the empty word. The only nonempty squarefree binary
words are 
, 
,
ab, ba, aba, and bab. Avoiding aa and bb
forces alternation, and every alternating word of length
four contains abab or baba.
of ternary squarefree words of length 
over a fixed three-letter alphabet
is given for 
,
1, 2, ... by 1, 3, 6, 12, 18, 30, 42, 60, ... (OEIS A006156).
The exponential growth rate exists and satisfies
![S=lim_(n->infty)[s(n)]^(1/n) approx 1.30176.](/images/equations/SquarefreeWord/NumberedEquation1.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.
Sci. 18, 221-226, 1982.Crochemore, M. "Tests sur les
morphismes faiblement sans carré." In 
th Power-Free Codes." In