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 -