How many different bit strings can be transmitted if the string must begin with a 1 bit, must include three additional 1 (so that a total of four 1 bits is sent), must include a total of 12 0 bits, and must have at least two 0 bits following each 1 bit ?
There are a total of 16 bits but we only need to worry about the last 13 since the first bit must be a 1 and followed by two zeros as such:
1 0 0 _ _ _ _ _ _ _ _ _ _ _ _ _
There are 3 more 1 bits followed by two zeros we must consider and the possible combinations are:
1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0
1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0
1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0
1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0
.....
.....
.....
and so on…
Since there are 13 bits to consider and 9 of those spots need to be arranged in the manner of a 1 bit followed by two 0 bits would the total possible number of combinations be C(13,9) ?
Best Answer
You have $3$ elements of the form $100$ and $4$ zeros to place in $13$ positions as you say (we ignore the first three because they are indeed fixed). So, by considering the element $100$ as a unity, you actually have $3$ (compounded) elements and $4$ zeros to place in $7$ positions. For example $$x \, 0 \, x \, 0 \,x \, 0 \, 0$$ stands for $$100\,0\,100\,0\,100\,0\,0$$You can do it in $$\dbinom{7}{3}=\frac{7!}{3!4!}=35$$ ways.