CODEWITHSUNDEEP
mathcomputer-sciencediscrete-mathematics
UnearthOS
UnearthOS

Reputation: 153

Discrete Mathematics bit string permutation query

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?

Upvotes: 0

Views: 1192

Answers (1)

jiulongw
jiulongw

Reputation: 355

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.

Upvotes: 2

Related Questions