How many bit strings of length 7 exist if the string remains unchanged if it is reversed?

Question

How many bit strings of length 7 exist if the string remains unchanged if it is reversed ?

1 1 1 1 1 1 1 and 1 0 0 1 0 0 1 are an example that is unchanged if reversed.

0 0 0 0 0 0 0 and 0 1 1 0 1 1 0 would then also be unchanged..

Is there some way to calculate this? or do I have to find all the 128 bit strings and reverse them to see if they fit?

Answer 1

So consider a string

1. a b c d e f g.

If we reverse this string we have

2. g f e d c b a.

Now by hypothesis the first digit of 1. corresponds to the first digit of 2, the second digit of 1. to the second digit of 2 as follows:

a b c d e f g
| | | | | | |
g f e d c b a

Thus, if and only if a bit string remains the same when reversed, then and only then a=g, b=f, and c=e. So, if we figure out how many bit strings of length 4 exist, we'll have figured out the answer. And more generally, if we have a bit strength of length x, then:

The number of palindromic bit strings of length x is equal to the number of bit strings of length

x/2 if x is even,

or the number of bit strings of length (x+1)/2 if x is odd.