Counting palindromic patterns

[ *January 13, 2001* ]

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**, ...