Andrew Tomazos <(E-Mail Removed)> writes:

> We want to count how many different N character strings over a 26-

> letter alphabet contain K or more M character palindrome substrings.

>

> For example, how many 3 character strings over a 26-letter alphabet

> contain 1 or more 2 character palindrome substrings?

>

> Well there is...

>

> { AAA, BAA, CAA, DAA, ..., ZBB, CCB, DDB, EEB, ..., YZZ, ZZZ }

>

> ...a total of 1326 different 3 character strings that contain a 2

> character palindrome.
There are 26 possible 2-character palindromes over a 26-letter

alphabet. There are 51 ways to embed each of these into a

3-character string (each can be preceded or followed by any

letter, but 2 of those are indistinguishable). Hence there are

26 * 51 == 1326 possibilities, as you say.

I suspect that this line of reasoning can be extended to larger

numbers, but I haven't tried.

--

Ben Pfaff

http://benpfaff.org