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

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

Table of n, a(n) for n=1..7.

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

Adjacent sequences: A269557 A269558 A269559 * A269561 A269562 A269563

Keyword

hard,more,nonn

Author

Jarkko Peltomäki, Feb 29 2016

Status

approved