##
**Improved Bounds on the Number of Ternary Square-Free Words**

###
Uwe Grimm

Applied Mathematics Department

Faculty of Mathematics and Computing

The Open University, Walton Hall

Milton Keynes MK7 6AA, UK

**Abstract:**
Improved upper and lower bounds on the number of square-free ternary
words are obtained. The upper bound is based on the enumeration of
square-free ternary words up to length 110. The lower bound is
derived by constructing generalised Brinkhuis triples. The problem
of finding such triples can essentially be reduced to a
combinatorial problem, which can efficiently be treated by computer.
In particular, it is shown that the number of square-free ternary
words of length n grows at least as 65^{n/40}, replacing the
previous best lower bound of 2^{n/17}.

**
Full version: pdf,
dvi,
ps,
latex,
Mathematica program
**

(Mentions sequence
A006156
.)

Received August 1, 2001;
revised version received October 1, 2001.
Published in Journal of Integer Sequences February 13, 2002.

Return to
**Journal of Integer Sequences home page**