Upper Bound for Palindromic and Factor Complexity of Rich Words

A finite word $w$ of length $n$ contains at most $n+1$ distinct palindromic factors. If the bound $n+1$ is attained, the word $w$ is called rich. An infinite word $w$ is called rich if every finite factor of $w$ is rich. Let $w$ be a word (finite or infinite) over an alphabet with $q>1$ letters, let $F(w,n)$ be the set of factors of length $n$ of the word $w$, and let $F_p(w,n)\subseteq F(w,n)$ be the set of palindromic factors of length $n$ of the word $w$. We present several upper bounds for $\mathrm{\mid }F(w,n)\mathrm{\mid }$ and $\mathrm{\mid }{F}_p(w,n)\mathrm{\mid }$, where $w$ is a rich word. In particular we show that $$\mathrm{\mid }F(w,n)\mathrm{\mid }\le (q+1)8n^2(8q^{10}n{)}^{{\log }_{2}2n}+q\mathrm{.}$$ In 2007, Bal{'a}{\v z}i, Mas{'a}kov{'a}, and Pelantov{'a} showed that $$\mathrm{\mid }{F}_p(w,n)\mathrm{\mid }+\mathrm{\mid }{F}_p(w,n+1)\mathrm{\mid }\le \mathrm{\mid }F(w,n+1)\mathrm{\mid }-\mathrm{\mid }F(w,n)\mathrm{\mid }+2,$$ where $w$ is an infinite word whose set of factors is closed under reversal. We generalize this inequality for finite words.