in Combinatory
126 views
1 vote
1 vote
A palindrome is a string whose reversal is identical to the string. How many bit strings of length $n$ are palindromes?
in Combinatory
126 views

1 Answer

1 vote
1 vote
Best answer

Ans: $2^{\lceil n/2 \rceil}$

APPROACH: 

for even length strings:


1st bit and nth bit are same. similarly, 2nd and (n-1)th bits are same.
Now, 2 bits for every position, and we are filling n/2 positions. therefore $2^{n/2}$ strings
 

for odd-length strings

1st bit and nth bit are same. similarly, 2nd and (n-1)th bits are same. but {(n+1)/2}th positions has 2 more ways to be filled
Now, 2 bits for every position, and we are filling n/2 positions. therefore $2^{n+1/2}$ strings.


We can also write it as $2^{\lceil n/2 \rceil}$.

selected by

Related questions