Properties of palindromes in finite words

Abstract

We present a method which displays all palindromes of a given length from De Bruijn words of a certain order, and also a recursive one which constructs all palindromes of length $n+1$ from the set of palindromes of length $n$. We show that the palindrome complexity function, which counts the number of palindromes of each length contained in a given word, has a different shape compared with the usual (subword) complexity function. We give upper bounds for the average number of palindromes contained in all words of length $n$, and obtain exact formulae for the number of palindromes of length 1 and 2 contained in all words of length $n$.