TY - JOUR

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

AU - Kostochka, A. V.

N1 - Funding Information:
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.

PY - 1998

Y1 - 1998

N2 - 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 xs+1 - qxs + 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.

AB - 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 xs+1 - qxs + 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.

UR - http://www.scopus.com/inward/record.url?scp=29444444749&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=29444444749&partnerID=8YFLogxK

U2 - 10.1515/dma.1998.8.2.109

DO - 10.1515/dma.1998.8.2.109

M3 - Article

AN - SCOPUS:29444444749

SN - 0924-9265

VL - 8

SP - 109

EP - 118

JO - Discrete Mathematics and Applications

JF - Discrete Mathematics and Applications

IS - 2

ER -