Discrete Mathematics bit string permutation query

Question

A bit string is a string over the alphabet {0, 1}. A palindrome is a string whose reversal is

identical to the string. How many bit strings of length 15 are palindromes that don’t start with

111?

This is math, not programing. How many length 15 palindromes are there? — Teepeemm
– Teepeemm, Commented Jan 10, 2015 at 0:42

jiulongw · Accepted Answer · 2015-01-10 01:25:50Z

2

starts with 111 must ends with 111 so there're 9 bits left.

The center bit can be either 0 or 1. For each case, there are 4 bits to the left which can have 16 possible values, and the right 4 bits must match the left 4 bits.

So all together 2 * 16 = 32.

Well, sorry it should be "don't start with 111". Then it should be 32 * 7 = 224 possible values.

edited Jan 10, 2015 at 1:25

answered Jan 10, 2015 at 0:30

jiulongw

3553 silver badges5 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

UnearthOS Over a year ago

thanks for the post but can you tell why did you multiply with 7

jiulongw Over a year ago

@UnearthOS excluding the first three bits, there are 32 possible values. First three bits have 8 possible values. One of the 8 value is excluded (111) so multiple by 7

Collectives™ on Stack Overflow

Discrete Mathematics bit string permutation query

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related