# Palindrome

• Jan 11th 2009, 12:15 AM
sana07
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?

I would really appreciate any help.
• Jan 11th 2009, 12:52 AM
mr fantastic
Quote:

Originally Posted by sana07
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?

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 ....
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 ....