Total palindrome complexity of finite words

The palindrome complexity function pal w of a word w attaches to each n ∈ N the number of palindromes (factors equal to their mirror images) of length n contained in w . The number of all the nonempty palindromes in a finite word is called the total palindrome complexity of that word. We present exact bounds for the total palindrome complexity and construct words which have any palindrome complexity between these bounds, for binary alphabets as well as for alphabets with the cardinal greater than 2. Denoting by M q ( n ) the average number of palindromes in all words of length n over an alphabet with q letters, we present an upper bound for M q ( n ) and prove that the limit of M q ( n ) / n is 0. A more elaborate estimation leads to M q ( n ) = O ( n ) .