Results 1 to 3 of 3

Math Help - [SOLVED] Palindromes (Tricky)

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    44

    [SOLVED] Palindromes (Tricky)

    How many binary strings of length n are palindromes?

    Now, I have come to the conclusion that it depends on whether n is even or odd because I just cant find a single formula for this otherwise.

    Even length = 2 ^ (n / 2).
    Odd Length im not sure. Can someone give me alittle hint or help on this.
    Ive been thinking about it for too long.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    May 2009
    Posts
    27
    Quote Originally Posted by kurac View Post
    How many binary strings of length n are palindromes?

    Now, I have come to the conclusion that it depends on whether n is even or odd because I just cant find a single formula for this otherwise.

    Even length = 2 ^ (n / 2).
    Odd Length im not sure. Can someone give me alittle hint or help on this.
    Ive been thinking about it for too long.
    You are correct for when n is even.

    Suppose n is odd. Then n=2k+1.
    A palindrome is entirely determined by the first k positions, as the last k must be the same in reverse. The middle position can be anything.

    So we have 2 choices for the middle positions, and 2^k choices for the first k positions. So there are 2\cdot 2^k=2^{k+1}=2^{(n-1)/2+1}=2^{(n+1)/2}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,865
    Thanks
    744
    Hello, kurac!

    How many binary strings of length n are palindromes?
    Both you and amitface are correct . . .

    . . \begin{array}{cc}\text{Even }n\!:& 2^{\frac{n}{2}} \\ \\[-3mm] \text{Odd }n\!: & 2^{\frac{n+1}{2}} \end{array}


    They can be merged into one function like this:

    . . f(n) \;=\;\frac{1+(\text{-}1)^n}{2}\cdot2^{\frac{n}{2}} + \frac{1-(\text{-}1)^n}{2}\cdot 2^{\frac{n+1}{2}}

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Palindromes
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 26th 2010, 09:28 PM
  2. Palindromes -
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 13th 2010, 10:54 AM
  3. Palindromes
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 5th 2009, 09:55 AM
  4. Palindromes
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 18th 2009, 02:15 PM
  5. Palindromes
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 26th 2007, 05:25 AM

Search Tags


/mathhelpforum @mathhelpforum