On the number of α-power-free binary words for 2<α≤7/3

AbstractWe study the number uα(n) of α-power-free binary words of length n, and the asymptotics of this number when n tends to infinity, for a fixed rational number α in (2,7/3]. For any such α, we prove a structure result that allows us to describe constructively the sequence uα(n) as a 2-regular sequence. This provides an algorithm that computes the number uα(n) in logarithmic time, for fixed α. Then, generalizing recent results on 2+-free words, we describe the asymptotic behaviour of uα(n) in terms of joint spectral quantities of a pair of matrices that one can efficiently construct, given a rational number α.For α=7/3, we compute the automaton and give sharp estimates for the asymptotic behaviour of uα(n)