A269560 Length of the longest squarefree and rich word over an alphabet of n letters.

1, 3, 7, 15, 33, 67, 145

Offset: 1

Author

Jarkko Peltomäki, Feb 29 2016

Keywords

• hard
• more
• nonn

Comments

A squarefree and rich word over a fixed alphabet always has bounded length (see Pelantová & Starosta). A word is squarefree if it does not contain squares as subwords, and a word of length n is rich if it contains exactly n+1 distinct palindromes (including the empty word) as subwords.

It is known that 2.008^n <= a(n) <= 2.237^n for n >= 5 (see Vesti).

Examples

			For n = 3, the longest squarefree and rich words are (up to isomorphism) 0102010 and 0121012. For n = 4, e.g., the word 010201030102010 has maximal length.
		

Links

• E. Pelantová, Š. Starosta, Languages invariant under more symmetries: overlapping factors versus palindromic richness, arXiv:1103.4051 [math.CO], 2011-2012.
• E. Pelantová, Š. Starosta, Languages invariant under more symmetries: overlapping factors versus palindromic richness, Discrete Mathematics, 313.21 (2013), 2432-2445.
• Jetro Vesti, Rich square-free words, arXiv:1603.01058 [math.CO], 2016.