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 kn k n be a sequence of positive integers. From [I. Tomescu, A threshold property concerning words containing all short factors, Bull. EATCS 64 (1998) 166170] it follows that if lim sup n ? ? k ( n ) / ln n   1 / ( 3 ln m ) then this property is false. Moreover, if limn??(lnn-3klnm)=??R lim n ? ? ( ln n - 3 k ln m ) = ? ? R then limn??|W(n,(aba)kn,A)|/mn=1-exp(-(1-1/m3)exp(?)) lim n ? ? | W ( n , ( aba ) k n , A ) | / m n = 1 - exp ( - ( 1 - 1 / m 3 ) exp ( ? ) ) , where W(n,(aba)kn,A) W ( n , ( aba ) k n , A ) denotes the set of words of length n over A  containing the factor (aba)kn ( aba ) k n .
word factor recurrence relation characteristic equation pseudo-vandermonde determinant