On the average number of regularities in a word (Q2437740)

This is a study on the average number of several types of regularities in a finite word. The regularities taken into account are: powers, runs, palindromes, abelian squares and abelian cubes. It is worth noticing that the authors refer to the average number of factors that verify each definition. So, for example, ``number of palindromes'' means the number of pairs \((i,j)\) such that the factor beginning in position \(i\) and ending in position \(j\) is a palindrome, and must not be confused with the number of \textit{distinct} palindromes appearing in a word. It is shown that a word of length \(n\) over an alphabet of cardinality \(\sigma>1\) contains, on average: {\parindent=6mm \begin{itemize}\item[--] \(\Theta(n)\) \(r\)-powers, for any \(r>1\), \item[--] \(O(n)\) runs (maximal repetitions), \item[--] \(\Theta(n)\) palindromes. \end{itemize}} Explicit bounds are also provided. Furthermore, bounds on the number of abelian squares and abelian cubes in a binary word are derived. It is shown that a binary word of length \(n\) contains \(\Theta(n^{3/2})\) abelian squares while the number of abelian cubes is expressed in terms of the Franel numbers \(\mathrm{Fr}_{n}=\sum_{i=0}^{n}\binom{n}{i}^{3}.\) A consequence of the result on the abelian squares is that the probability that a binary word contains not more that \(n^{3/2}\) abelian squares tends to \(1\) as \(n\) tends to \(\infty\). The proofs are quite standard and are based on the computation of the expectation of a discrete random variable. However, some notations used in the paper are non-standard, for example \([n \mod 2 =0]\) stands for \((1-n \mod 2)\).