On Number of Rich Words

Abstract

Any finite word $w$ of length $n$ contains at most $n+1$ distinct palindromic factors. If the bound $n+1$ is reached, the word $w$ is called rich. The number of rich words of length $n$ over an alphabet of cardinality $q$ is denoted $R_n(q)$. For binary alphabet, Rubinchik and Shur deduced that $R_n(2)\le c1.605^n$ for some constant $c$. We prove that $\underset{n\to \infty }{\lim }\sqrt[n]{R_n(q)}=1$ for any $q$, i.e. $R_n(q)$ has a subexponential growth on any alphabet.

References in corpus (3)

• On the Combinatorics of Palindromes and Antipalindromes
• Extensions of rich words
• The Number of Distinct Subpalindromes in Random Words

Cited by in corpus (3)

• Upper Bound for Palindromic and Factor Complexity of Rich Words
• Palindromic factorization of rich words
• Double-Ended Palindromic Trees in Linear Time