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)

URL: http://www.cs.uwaterloo.ca/journals/JIS/VOL4/GRIMM...

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

Viewing alternatives

Item Actions

Export

You can export this page using these formats

About

• Item ORO ID
• 6744
• Item Type
• Journal Item
• 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 or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Depositing User
• Uwe Grimm