Property of upper bounds on the number of rich words

Josef Rukavicka

Published 2022-12-18Version 1

A finite word $w$ is called \emph{rich} if it contains $\vert w\vert+1$ distinct palindromic factors including the empty word. Let $q\geq 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 $\phi, \psi$ be real functions such that \begin{itemize}\item there is $n_0$ such that $2\psi(2^{-1}\phi(n))\geq d\psi(n)$ for all $n>n_0$, \item $\frac{n}{\phi(n)}$ is an upper bound on the palindromic length of rich words of length $n$, and \item $\frac{x}{\psi(x)}+\frac{x\ln{(\phi(x))}}{\phi(x)}$ is a strictly increasing concave function. \end{itemize} We show that if $c_1,c_2$ are real constants and $R(n)\leq q^{c_1\frac{n}{\psi(n)}+c_2\frac{n\ln(\phi(n))}{\phi(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\psi(n)}+c_2\frac{n\ln(\phi(n))}{\phi(n)}(1+\frac{1}{c_2\ln{q}}+c_3)}\mbox{.}\]