Results 1 to 2 of 2

Math Help - Palindrome

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    1

    Unhappy Palindrome

    A palindrome is a string which, when reversed it is identical to the original string, eg. 0110 is a palindrome and 0100 is not. How many bit strings of length n are palindromes?

    Please help me with this question.

    I would really appreciate any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by sana07 View Post
    A palindrome is a string which, when reversed it is identical to the original string, eg. 0110 is a palindrome and 0100 is not. How many bit strings of length n are palindromes?

    Please help me with this question.

    I would really appreciate any help.
    n even:

    Spilt the string in half. The first n/2 characters can be either 0 or 1 so there are 2^{n/2} arrangements. You require the second half to be the reverse of the first half and there's only 1 way that can happen. Therefore ....

    n odd:

    The middle character can be 0 or 1 so there's 2 possibilities for the middle.
    The characters to the left of the middle character can be either 0 or 1 so there's 2^{(n-1)/2} arrangements. You require the characters to the right of the middle character to be the reverse of the characters to the left and there's only 1 way that can happen. Therefore ....
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. smallest five-digit palindrome
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: January 10th 2011, 04:34 AM

Search Tags


/mathhelpforum @mathhelpforum