login
A269560
Length of the longest squarefree and rich word over an alphabet of n letters.
0
1, 3, 7, 15, 33, 67, 145
OFFSET
1,2
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).
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.
EXAMPLE
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.
CROSSREFS
Sequence in context: A134195 A365527 A079444 * A146654 A363503 A193641
KEYWORD
hard,more,nonn
AUTHOR
Jarkko Peltomäki, Feb 29 2016
STATUS
approved