The Open UniversitySkip to content

Improved bounds on the number of ternary square-free words

Grimm, Uwe (2001). Improved bounds on the number of ternary square-free words. Journal of Integer Sequences, 4(2)

Full text available as:
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (133Kb)
Google Scholar: Look up in Google Scholar


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).

Item Type: Journal Article
ISSN: 1530-7638
Extra Information: The Journal of Integer Sequences is an open access journal without consecutive page numbers. The article number is 01.2.7.
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Mathematics, Computing and Technology
Item ID: 6744
Depositing User: Uwe Grimm
Date Deposited: 13 Feb 2007
Last Modified: 21 Jan 2016 23:33
Share this page:

Actions (login may be required)

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340