Number of binary strings of P 0's and Q 1's such that every pair of 1's is separated by at least 2 0's

45 Views Asked by At

This question has been stumping me. I'm not sure how to go about enumerating the different possibilities.


I came up with a solution for Q=2 that suggests the problem needs some inclusion-exclusion type solution. (P+Q choose Q)-(P+Q-1)-(P+Q-2)? I checked for $P=5, Q=2$. The thought is that we first count all the placements of 1's, then remove the invalid cases, of which there are those where we have a pair of 1's adjacent, (P+Q-1), and those where we have a 0 and 1 separated by one 0, (P+Q-2).

2

There are 2 best solutions below

0
On

Let $n_0$ denote the number of zeros at the left of the utmost left one, and let $n_q$ denote the number of zeros at the right of the utmost right one.

Further for $1\leq k\leq q-1$ let $n_k$ denote the number of zeros between the $k$-th and the $k+1$-th zero, reading from left to right.

To be found is the number of sums $\sum_{k=0}^qn_k=p$ where $n_0$ and $n_q$ are nonnegative integers and where for $1\leq k\leq q-1$ the $n_k$ are integers $\geq2$.

That comes to the same as finding the number of sums $\sum_{k=0}^qm_k=p-2(q-1)$ where $m_k$ is a nonnegative integer for every $k$.

This can be solved by applying stars and bars.

Give it a try yourself.

0
On

Consider a string of length $n$, with $p$ ones and $q=n-p$ zeros.
Append to the end two dummy zeros.

Str_bin_100_1

Now, since the $1$'s shall be separated by at least two zeros, we can consider the $1$'s in a block together with two zero's on its right.

Then we have $n+2-3*p$ places where to put $p$ blocks, and we have better to write the number of ways to do that as $$ \binom{n+2-3p}{n+2-4p}$$