# Discrete mathematics bit strings

So my question is that let's say I have a bit string of length four. If it is illegal to have 3 1's in a row and 3 0's in a row then how many bit string of this type exists

I was thinking that in total combination of bit strings of length four there is $2^4$, but in this case there is 2+2 illegal combinations so the total is

$2^4-4$ is this correct?

• Yes that's correct. Mar 17 '18 at 21:05
• Are $0000$ and $1111$ allowed? Mar 17 '18 at 21:09

No. There are $6$ illegal strings. Just write them out. Unless 'three in a row' means exactly three in a row ... but that's not how I would interpret that question ...
• so it should be $2^4-6$? Mar 17 '18 at 21:10