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

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?

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