CLR cover
Previous problem

Problem 13: Many Words with Many Palindromes

Next problem

The problem deals with the number of words containing as many palindrome factors as possible. A word $w$ is called palindrome rich if it contains $|w|$ distinct non-empty palindromes as factors, including single-letter palindromes.

Let $\Rich_k(n)$ denote the number of rich words of length $n$ over an alphabet of size $k$.

Note that each position on a word is the (starting) position of the rightmost occurrence of a palindrome that it contains at most once. This is due to the fact that a second shorter palindrome sharing the position would be a proper suffix of the longer palindrome and then would occur later, a contradiction. This implies the following fact.

Observation. There are at most $|w|$ palindromes, factors of a word $w$.

The most interesting case to discuss is that of binary words, that is, $k=2$, because we have \[\cases{ \Rich_2(n)=2^n & for $n<8$, \cr \Rich_2(n)\lt 2^n & for $n\geq 8$. }\]

Show that $\Rich_2(2n)$ grows exponentially; that is, there is a positive constant $c$ for which $\Rich_2(2n)\geq 2^{c n}$.

References

  • A. Glen, J. Justin, S. Widmer, and L. Q. Zamboni. Palindromic richness. Eur. J. Comb., 30(2):510-531, 2009.