[ January 13, 2001 ]
Counting palindromic patterns
Marks R. Nester

Marks R. Nester from Australia investigated thoroughly palindromic structures
and made various integer sequences resulting from the count.
I felt that this topic is so basic for my palindrome website that
it should have appeared much earlier... but 'better late than never' the saying goes.
(Source: see Sloane's integer sequences A056449 up to A056523)
The description of, for instance A056450, is as follows
Palindromes using a maximum of four different characters.
The "palindromicy" refers to the number of palindromes
that one can make using an alphabet of four letters.
Suppose a, b, c, d are the only letters in our alphabet.
Then for words of length 1 the only (trivial) palindromes
are the letters themselves, i.e.
a, b, c, d. (4 altogether)

For words of length 2 the only palindromes are:
aa, bb, cc, dd. (4 altogether)

For words of length 3 the only palindromes are:
aaa, aba, aca, ada,
bab, bbb, bcb, bdb,
cac, cbc, ccc, cdc,
dad, dbd, dcd, ddd.
(16 altogether)

etc...

Proceeding in this fashion we obtain the sequence
4, 4, 16, ...