Property of upper bounds on the number of rich words

Abstract

A finite word $w$ is called \emph{rich} if it contains $|w|+1$ distinct palindromic factors including the empty word. Let $q\ge 2$ be the size of the alphabet. Let $R(n)$ be the number of rich words of length $n$. Let $d>1$ be a real constant and let $\varphi ,\psi$ be real functions such that \begin{itemize}\item there is $n_0$ such that $2\psi (2^{-1}\varphi (n))\ge d\psi (n)$ for all $n>n_0$, \item $\frac{n}{\varphi (n)}$ is an upper bound on the palindromic length of rich words of length $n$, and \item $\frac{x}{\psi (x)}+\frac{x\ln (\varphi (x))}{\varphi (x)}$ is a strictly increasing concave function. \end{itemize} We show that if $c_1,c_2$ are real constants and $R(n)\le q^{c_1\frac{n}{\psi (n)}+c_2\frac{n\ln (\varphi (n))}{\varphi (n)}}$ then for every real constant $c_3>0$ there is a positive integer $n_0$ such that for all $n>n_0$ we have that \[R(n)\leq q^{(c_1+c_3)\frac{n}{dψ(n)}+c_2\frac{n\ln(ϕ(n))}{ϕ(n)}(1+\frac{1}{c_2\ln{q}}+c_3)}\mbox{.}\]