How many string of 16 bit can we build having the following constraints:
- There must be exactly 5 one
- Between two 1 there must be at least two 0.
Example of valid string:
(1) 1 00 1 00 1 00 1 00 1 000
(3) 0 1 00 1 00 1 00 1 00 1 00
(3) 1 0000 1 00 1 00 1 000 1
I have no clue how to approach problems like these. I know the answer (which is 56) but I do not know the logic behind that.
Because the length of the string is 16 and there are $5$ ones, there must be $11$ zeros.
Now, place the ones on the line, as _ $1$ _ $1$ _ $1$ _ $1$ _ $1$ _, we have 2 gaps at each end, and 4 gaps in the middle of the ones, for a total of 6 gaps. Now denote the number of zeros in each gap $g_i$, with $ i \in \{1,2,3,4,5,6 \}$, then from the given conditions, $g_2,g_3,g_4,g_5$ must be larger than or equal to $2$, and thus $G_i=g_i -2 \ge 0$ for all $i \in \{ 2,3,4,5 \}$
So we have the sum $ g_1 +G_2 +G_3+G_4+G_5 +g_6 = 3$, which means divide $3$ balls in to $6$ groups, each group might have a non-negative number of balls. The formula for this division is $ \binom {8}{3}$, which you may see the explanation in the Star and Bar link mentioned above