Question

How many bit strings of length 12 contain the substring "111000"?

Answer 1

Each bit can be fill by 2 ways either 0 or 1. Out of the 12 bits we need a substring of length 6 which is '111000'

So, first we select the bit from where it can start. So, it can come from 1st bit to 7th bit as after that there will not be 6 bits to fill in. So, there is 7 ways to put this substring.

Then in the remaining 6 bits each can be filled by 2 ways.

Hence, total ways =

Hence, 448 strings of length 12 contain the substring '111000'.

Please comment if any doubt. Thank you.