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!

Palindrome with 5 letters

  1. May 15, 2010 #1
    Hi,

    Here is a weird question (I hope you don't mind).

    Let's say we have an alphabet with only 4 letters (A, B, C, D)? How many combinations of give us palindromes (i.e. they read the same way backwards and forwards)? I count 36 possible combinations -
    AAAA BAAB CAAC DAAD EAAE FAAF
    ABBA BBBB CBBC DBBD EBBE FBBF
    ACCA BCCB CCCC DCCD ECCE FCCF
    ADDA BDDB CDDC DDDD EDDE FDDF
    AEEA BEEB CEEC DEED EEEE FEEF
    AFFA BFFB CFFC DFFD EFFE FFFF

    This is the same number with an alphabet of only 3 letters -.
    AFA, AEA, ADA, ACA, ABA, AAA
    BFB, BEB, BDB, BCB, BBB, BAB
    CFC, CEC, CDC, CCC, CBC, CAC
    DFD, DED, DDD, DCD, DBD, DAD
    EFE, EEE, EDE, ECE, EBE, EAE
    FFF, FEF, FDF, FCF, FBF, FAF

    Is that right?

    Now, how about an alphabet with 5 letters? Is there any equation that can be used to determine the number of palindromes, or do I need to use a computer algorithm to work it out.

    Thanks,
    Maria
     
  2. jcsd
  3. May 15, 2010 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Maria! :smile:

    This should help you to find the formula …

    If the word-length is 2n (even), then the number of palindromes is the same as the number of ordinary words of length n.

    If the word-length is 2n - 1 (odd), then the number of palindromes is the same as the number of palindromes of length 2n, since you just double the central letter. :wink:
     
  4. May 15, 2010 #3

    Borek

    User Avatar

    Staff: Mentor

    You need to add some limit to the word length. Answer to the question as stated is "infinitely many". Take any, add the same letter at the end and at the beginning, and you have a new palindrome. Repeat ad nauseam.
     
  5. May 15, 2010 #4
    Why do you also use the letters E and F? I thought your alphabet consists only of the letters A,B,C,D.

    To find the number of combinations write down what a palindrome is in general:
    xyyx
     
  6. May 15, 2010 #5


    Additionally, your examples are only 4 letters, not 5.

    As shown above, you just need the pattern xy and pair it with it's reverse to get xyyx.

    How many xy patterns are there? That's the Cartesian Product of 4 letters taken 2 at a time.

    That would be (length of alphabet) * (length of alphabet).
    (Or in general, (length of alphabet)**(length of pattern).)

    The number of xy patterns is (4*4).

    To get 5 letter palindromes, you need to use the pattern xyzyx, so you would need to multiply the number of xy patterns by the length of the alphabet.

    Thus, the number of xyzyx patterns is (4*4)*4.

    Which can be generated thusly:
    Code (Text):
    # Python 3.1
    import itertools as it
    count = 0
    alpha = 'abcd'
    for h in alpha:
      for i in it.product(alpha,alpha):
        j = ''.join(i)
        k = ''.join(reversed(j))
        print(j+h+k)
        count += 1
    print(count)
     
    aaaaa ababa acaca adada baaab bbabb bcacb bdadb caaac cbabc ccacc cdadc daaad dbabd dcacd ddadd aabaa abbba acbca adbda babab bbbbb bcbcb bdbdb cabac cbbbc ccbcc cdbdc dabad dbbbd dcbcd ddbdd aacaa abcba accca adcda bacab bbcbb bcccb bdcdb cacac cbcbc ccccc cdcdc dacad dbcbd dcccd ddcdd aadaa abdba acdca addda badab bbdbb bcdcb bdddb cadac cbdbc ccdcc cdddc dadad dbdbd dcdcd ddddd
    64

     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook