## Example

\(
\def\sa#1{\tt{#1}}
\newcommand{\Rich}{\mathit{Rich}}%
\)

The words $\sa{poor}$, $\sa{rich}$ and $\sa{abac}$ are rich, while the words
$\sa{maximal}$ and $\sa{abca}$ are not.
Indeed, the set of palindromes occurring
in $\sa{abac}$ is $\{\sa{a},\sa{aba},\sa{b},\sa{c}\}$, while it is
$\{\sa{a},\sa{b},\sa{c}\}$ for $\sa{abca}$.

#
Problem 13: Many Words with Many Palindromes

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.