Let $R(n)$ denote the number of rich words of length $n$ over a given finite alphabet. In 2017 it was proved that $\lim_{ n\rightarrow\infty} \sqrt[n]{ R(n)}=1$; it means the number of rich words has a subexponential growth. However, up to now, no subexponential upper bound on $R(n)$ has been presented. The current paper fills this gap. Let $\frac{ 1}{ 2}<\lambda<1$ and $\gamma>1$ be real constants, let $q$ be the size of the alphabet, and let $\phi$ be a positive function with $\lim_{ n\rightarrow\infty}\phi(n)=\infty$ and $\lim_{ n\rightarrow\infty}\frac{ n}{ \phi(n)}=\infty$. Let $\ln^*(x)$ denote the iterated logarithm of $x>0$. We prove that there are $n_0$ and $c>0$ such that if $n>n_0$, \[f(n)=\sqrt[\gamma]{ c\ln^*{ (\frac{ n}{ \phi(n)}}\ln{ q})}\quad\mbox{ and }\quad B(n)=q^{ \frac{ n}{ \phi(n)}+\frac{ n}{ (2\lambda)^{ f(n)-1}}}\mbox{ }\] then $\lim_{ n\rightarrow\infty}\sqrt[n]{ B(n)}=1$ and $R(n)\leq B(n)$.
Categories: math.CO cs.DM