Explore BrainMass


How many bit strings of length n are palindromes? Hint: Consider two cases n is even and n is odd. Note a palindrome is a "string" of letters or numbers which read the same frontwards and backwards. Examples: MOM, 1101011, 10111101 are palindromes.

© BrainMass Inc. brainmass.com June 22, 2018, 9:11 am ad1c9bdddf

Solution Preview

Hello and thank you for posting your question to BrainMass.

Let's see first how many different strings we can make with k bits.

If we have one bit, then we have two possible strings (namely "0" and "1")
If we have k=2 bits, then we have to possibilities for the first bit and two possibilities for the second bit, so together there are 2x2 = 4 possibles strings.
In a k length string, each bit has two possible values, hence the total number of strings is 2x2x.....2 = 2^k

Now we can start with out palindrome strings of length n.
Say we set the k<n bit. Then, by the definition of the palindrome this immediately sets the ...

Solution Summary

String bits and palindromes are assessed in this solution.