In: Math
A palindrome is a string whose reversal is identical to the string. For example, 110010011 is a palindrome. So are BOB and KAYAK. How many bit strings of length ?? are palindromes? Explain your solution clearly.
Here we need to consider two cases.
Case 1: If n is odd. Then leaving middle digit we can divide the string in to parts each having digits (n-1) / 2.
Let us consider first half that have (n-1)/2 digits. Each of these (n-1)/2 digit can be filled in 2 ways either from 1 or 0. So possible number of ways of filling first half of string is
Now, second half can be filled only way by reversing the digit of first half. Middle digit can be filled in 2 ways. So possible number of strings that are palindrome is
Case 2: If n is even. Then we can divide the string in to parts each having digits (n) / 2.
Let us consider first half that have (n)/2 digits. Each of these (n)/2 digit can be filled in 2 ways either from 1 or 0. So possible number of ways of filling first half of string is
Now, second half can be filled only way by reversing the digit of first half.So possible number of strings that are palindrome is