Affiliations: [a] Ural Federal University, Ekaterinburg, Russia. [email protected] | [b] Ural Federal University, Ekaterinburg, Russia. [email protected]
Correspondence:
[*]
Address for correspondence: Ural Federal University, Ekaterinburg, Russia
Abstract: We prove that a random word of length n over a k-ary fixed alphabet contains, on expectation, Θ(n) distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit limn→∞Ε(n,k)/n does not exist for any k ≥ 2, liminfn→∞Ε(n,k)/n=Θ(1), and limsupn→∞Ε(n,k)/n=Θ(k). Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.
