3 votes 3 votes A palindrome is a string whose reversal is identical to the string. How many bit strings of length n are palindromes? 2⌈n⁄2⌉ 2(⌊ n/2⌋ ) 2⌈n⁄2⌉ -1 2(⌊ n/2⌋) -1 Combinatory counting combinatory + – Akriti sood asked Nov 7, 2016 • retagged Jun 27, 2017 by Arjun Akriti sood 6.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes 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 Prashant. answered Nov 7, 2016 Prashant. comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes 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) Sourav Basu answered Apr 25, 2017 Sourav Basu comment Share Follow See all 2 Comments See all 2 2 Comments reply A_i_$_h commented Sep 11, 2017 reply Follow Share 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 0 votes 0 votes syed qamar commented May 23, 2018 reply Follow Share 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) 0 votes 0 votes Please log in or register to add a comment.