On the average number of regularities in a word
We study the average number of powers and runs occurring in a word of length n drawn from an alphabet of size ? . We show that a word contains n ? ( r ? 1 ) ? 1 + o ( n ) powers of exponent r , at most n ? + o ( n ) runs, and also ( 1 + 2 ? ? 1 ) n + o ( n ) palindromes. We also explore their abelian variants and prove that a binary word contains ? ( n 3 2 ) abelian squares on the average, while its number of abelian cubes is related to Franel numbers. Finally, as a consequence, we show that a binary word has almost surely O ( n 3 2 ) abelian squares.
regularities words powers runs palindromes abelian