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