  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$.
