The number of Q-ary words with restrictions on the length of the maximal run

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 λ where A is the greatest real root of the polynomial x^s+1 - qx^s + q - 1. A representation of λ 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 → ∞ 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.