Question

A palindrome is a string whose reversal is identical to the string. How many bit strings of length n are palindromes?

1.   2^⌈n⁄2⌉
2.   2^{(⌊ n/2⌋ )}
3.   2^⌈n⁄2⌉ -1
4.   2^{(⌊ n/2⌋)} -1

Answer 1

Try with N= 2 you get aa,bb 2^⌈n⁄2⌉  = 2

Try with N= 3 you get aaa,bbb ,aba , bab  2^⌈n⁄2⌉  = 4

Try with N= 4 you get aaaa,bbbb ,abba , baab , 2^⌈n⁄2⌉  = 4

A is answer

Answer 2

The trick here is to realize that a palindrome of length n is completely determined by its first ceiling(n/2)  bits.
This is true because once these bits are specified, the remaining bits, read from right to left, must be identical
to the first floor(n/2) bits, read from left to right. Furthermore, these first ceiling(n/2) bits can be specified at will,
and by the product rule, there are 2^ceiling(n/2) ways to do so. Hence answer is 2^ceiling(n/2)--> Option (A)

Comments

for even length its right

but for odd length N=3 how come ur getting 4??

considering aba..it can only be two ways

that is position of a can be in two places

so for odd it should be floor(n/2) right??

please correct me

---

if N is an odd number then then we have to use 2^[(n+1)/2]

if N is an Even number then we use 2^(n/2)