On the Entropy and Letter Frequencies of Ternary Square-Free Words

2003/02/28 by Christoph Richard, Uwe Grimm
Mathematics · Physics and Astronomy · #math.CO #math-ph #math.MP #msc:68R15 #msc:05A15

paper · pdf

published as The Electronic Journal of Combinatorics 11 (2004) #R14 · 17 pages, 2 figures

arxiv created 2003/03/19 · arxiv updated 2009/11/30

Abstract

We enumerate all ternary length-l square-free words, which are words avoiding squares of words up to length l, for l<=24. We analyse the singular behaviour of the corresponding generating functions. This leads to new upper entropy bounds for ternary square-free words. We then consider ternary square-free words with fixed letter densities, thereby proving exponential growth for certain ensembles with various letter densities. We derive consequences for the free energy and entropy of ternary square-free words.

Related

• The entropy of square-free words
• Lengths of extremal square-free ternary words
• A ternary square-free sequence avoiding factors equivalent to abcacba
• Improved bounds on the number of ternary square-free words
• There are More Than 2**(n/17) n-Letter Ternary Square-Free Words