On the number of words containing the factor (aba)k(aba)k

In this paper a recurrence relation satisfied by the number L(n)L(n) of words of length n over an alphabet A of cardinality m  (m⩾2)(m⩾2) not containing the factor (aba)k(aba)k(a≠b)(a≠b) is deduced. Let knkn be a sequence of positive integers. From [I. Tomescu, A threshold property concerning words containing all short factors, Bull. EATCS 64 (1998) 166–170] it follows that if limsupn→∞k(n)/lnn<1/(3lnm) then almost all words of length n over A   contain the factor (aba)kn(aba)kn as n→∞n→∞. Using the properties of the roots of the recurrence satisfied by L(n)L(n) it is shown that if limsupn→∞k(n)/lnn>1/(3lnm) then this property is false. Moreover, if limn→∞(lnn-3klnm)=η∈Rlimn→∞(lnn-3klnm)=η∈R then limn→∞|W(n,(aba)kn,A)|/mn=1-exp(-(1-1/m3)exp(η))limn→∞|W(n,(aba)kn,A)|/mn=1-exp(-(1-1/m3)exp(η)), where W(n,(aba)kn,A)W(n,(aba)kn,A) denotes the set of words of length n over A   containing the factor (aba)kn(aba)kn.