Число $q$-ичных слов с ограничениями на длину максимальной серии

Установлено, что число $g(q,s,n)$ слов длины $n$ в $q$-буквенном алфавите таких, что длина любого подслова из стоящих рядом одинаковых букв не превосходит $s$, весьма близка к $\lambda^n$, где $\lambda$ – наибольший действительный корень полинома $x^{s+1}-qx^s+q-1$. Найдено предствление $\lambda$ в виде суммы ряда. Результаты позволяют вычислять асимптотические значения $g(q,s,n)$ и функции $h(q,s,n)=g(q,s,n)-g(q,s-1,n)$ при $n\to\infty$ и $s>c\log n$ для любого фиксированного $c>0$.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проекты 96–01–01614, 96–01–01893 и 96–01–01496 соответственно для каждого из авторов.