The number of $q$-ary words with restrictions on the length of a maximal series

A. V. Kostochka ; V. D. Mazurov ; L. Ja. Savel'ev

Diskretnaya Matematika, Tome 10 (1998) no. 1, pp. 10-19.

Résumé

It is proved that the number $g(q,s,n)$ of words of length $n$ over a $q$-letter alphabet such that the length of any subword consisting of one and the same letter is no greater than $s$ is very close to $\lambda^n$, where $\lambda$ is the greatest real root of the polynomial $x^{s+1}-qx^s+q-1$. A representation of $\lambda$ in the form of a series is found. The results obtained let us calculate asymptotical values of $g(q,s,n)$ and the function $h(q,s,n)=g(q,s,n)-g(q,s-1,n)$ as $n\to\infty$ for $s>c \log n$, where $c$ is an arbitrary positive constant.The research was supported by the Russian Foundation for Basic Research, grants 96–01–01614, 96–01–01893, and 96–01–01496, respectively, for each of the authors.