Information and Computation 205 (2007) 1295–1306
wwwelseviercom/locate/ic
Exponential lower bounds for the number of words
of uniform length avoiding a pattern
Jason P Bell a,∗ , Teow Lim Goh b
aDepartment of Mathematics, Simon Fraser University, 8888 University Dr, Burnaby, BC, Canada V5A 1S6 bDepartment of Mathematics, University of Michigan, East Hall, 525 East University Ave, Ann Arbor, MI 481091109, USA
Received 16 May 2005; revised 8 January 2007
Available online 28 February 2007
Abstract
We study words on a ﬁnite alphabet avoiding a ﬁnite collection of patterns Given a patternpin which every letter that
occurs inpoccurs at least twice, we show that the number of words of lengthnon a ﬁnite alphabet that avoidpgrows expo
nentially withnas long as the alphabet has at least four letters Moreover, we give lower bounds describing this exponential
growth in terms of the size of the alphabet and the number of letters occurring inp We also obtain analogous results for
the number of words avoiding a ﬁnite collection of patterns We conclude by giving some questions
© 2007 Elsevier Inc All rights reserved
Keywords:Pattern avoidance; Combinatorics on words; Avoidable patterns
1 Introduction
LetXbe a ﬁnite alphabet and letpbe a word on some other alphabetY We say that a word inXavoids
the patternpif it contains no subword of the formh(p), wherehis a nonerasing homomorphism from the free
monoidY
∗generated byYto the free monoidX ∗generated byX We say thatpisavoidable onXif there are
inﬁnitely many words that avoid the patternp We say that a patternpisavoidableif it is avoidable on some
ﬁnite alphabet The Zimin algorithm [8, Section 32] is a recursive algorithm that determines if a given pattern
is avoidable or unavoidable Given a patternpon an alphabetY, we deﬁne
S(p,X)={h(p)|h:Y
∗→X ∗is a nonerasing homomorphism}(11)
We say that a wordWon the alphabetXisof the formpifW∈S(p,X)
The study of pattern avoidance began in the early 1900s with Thue’s work on squarefree words [14, 15] (see
also Nagell et al [11]) A word on a ﬁnite alphabetXissquarefreeif it contains no subword of the formww, where
wis a nonempty word onX Equivalently, a word is squarefree if it avoids the patternt
2 Squarefree words have
seen numerous applications over the years In group theory, they have been used in giving a counterexample
∗Corresponding author
Email addresses:

[email protected] (JP Bell),

[email protected] (TL Goh)
08905401/$ see front matter © 2007 Elsevier Inc All rights reserved
doi:101016/jic200702004
1296JP Bell, TL Goh / Information and Computation 205 (2007) 1295–1306
to the unrestricted Burnside problem [1] An interesting application to unending chess appears in Morse and
Hedlund [10] Much work has been done on counting squarefree words over various alphabets [3, 12] More gen
erally, one can look at words that avoid the patternt
jfor somej 2 Work on this problem has been done by
Brandenburg [4] and Bean et al [2] An excellent survey of pattern avoidance is found in Chapter 3 of Lothaire
[8] In addition to this, Currie [5, 6] has given many interesting open problems on the topic of pattern avoidance
We note that ifa(n)denotes the number of words of lengthnon an alphabetXwhich avoid some pattern or
collection of patterns, thena(n)issubmultiplicative; that is,a(n+m)
a(n)a(m) Sincea(n)is a submultiplica
tive sequence of natural numbers, Fekete’s lemma (cf Madras and Slade [9, Lemma 122]) shows that
lim
n→∞ a(n) 1/n
exists and is equal to some nonnegative real number When this limit is greater than 1, the number of words
a(n)of lengthnthat avoid our given collection of patterns grows exponentially In this paper, we show that
for a large class of avoidable patterns, this exponential growth phenomenon occurs Speciﬁcally, we look at
patternspon some ﬁnite alphabet with the property that every letter in the alphabet occurs at least twice inp
Such patterns are known to be avoidable [8, Cor 3210] We are able to give exponential lower bounds and thus
obtain a stronger result
Theorem 1Letpbe a pattern onk
2letters in which every symbol occurs at least twiceThen form 4and
(k,m)=(2, 4)there are at least(k,m) nwords of lengthnon anmletter alphabet that avoidp,where
(k,m):=m
1+1
(m−2) k
−1 (12)
We note that