Question

How many bit strings of length 10 contain either five con- secutive 0s or five consecutive 1s?

Answer 1

Observe first 5 consecutive 0s

Summation rule: the first 5 consecutive 0’s could start at position 1, 2, 3, 4, 5, or 6

Start at first position

Other 5 bits can be anything: 2^5 = 32

Start at second position

First bit must be a 1

There are various possibilities that can be included in it.

Remaining bits can be anything: 2^4 = 16

Start at third position

Second bit must be a 1 due to above mentioned reason.

First bit and last 3 bits can be anything: 2^4 = 16

Starting at 4,5 and 6 positions

Same as starting at positions 2 or 3: 16 each

Total = 32 + 16 + 16 + 16 + 16 + 16 = 112

The five consecutive 1’s ensue the same pattern, and have different like 112 possibilities

There would be two cases counted twice (that we thus need to exclude): 0000011111 and 1111100000

Total = 112 + 112 – 2 = 222