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 August 16, 2018, 7:13 pm 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.