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: 24 Feb 2016 10:42
Share this page:

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

▼ Automated document suggestions from open access sources

Actions (login may be required)

Policies | Disclaimer

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