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

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)109-118
Number of pages10
JournalDiscrete Mathematics and Applications
Volume8
Issue number2
DOIs
StatePublished - 1998
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The number of Q-ary words with restrictions on the length of the maximal run'. Together they form a unique fingerprint.

Cite this