1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting Palindromes

  1. Feb 19, 2009 #1
    The problem statement
    There are 26 letters in the English Alphabet, how many seven-letter palindromes can be made?


    The attempt at a solution
    There are 26 letters in the alphabet, so there are 26^7 possible
    strings of length 7 (order being important for palindromes, i don't
    think 26 choose 7 is appropriate).

    One way to do this would be to subtract the number of strings that are not palindromes from 26^7, but I have no idea how to get this number.

    Another way to do it is to figure out how many palindromes
    match the following cases:

    7 of the same letter: 26 cases
    6 of the same letter: 26*25 cases
    5 of the same letter: ? cases
    4 of the same letter: (ex: XXYZYXX)
    3 of the same letter: (ex: YZXXXZY)
    2 of the same letter: (ex: ZYXWXYZ)

    Since after the first two cases, there are multiple ways to arrange
    all of the letters that work, i get confused. (for example, 5 can be
    arranged as XXYXYXX, or XYXXXYX, or YXXXXXY)

    I know if I add all the cases together, i'll get the correct answer,
    (subtracting overlap), but this gets out of hand very quickly. Is
    there another approach that will work?
     
  2. jcsd
  3. Feb 20, 2009 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    You could start by noting that a seven letter palindrome should look like
    ABCDCBA
    where A, B, C, D are any letter from the English alphabet.
     
  4. Feb 20, 2009 #3
    Ah, I see.

    So you have 26 choices for A, 25 choices for B, 24 choices for C, and 23 choices for D.

    26*25*24*23 = 358800?

    EDIT: Actually, the above is incorrect, A, B, C , and D can all be the same.

    is 26^4 correct? That seems like it would be over counting, or counting some possibilities multiple times?
     
  5. Feb 20, 2009 #4

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    I would say 26^4, yes.
    Which two words, for example, would be overcounted then?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Counting Palindromes
  1. Palindrome Java Program (Replies: 12)

Loading...