How many binary strings with at least $k$ ones and every two of them are not adjacent?

Question

I only know how to solve this using dynamic programming technique with three parameters ($n$, $m$, $last$), where $n$ - is it the length of prefix that we examined, $m$ is the number of ones that we have on this prefix, and $last$ is the last digit we got in our binary prefix.

$f(n, m, last)$ - number of binary strings of length n with at least $k$ ones, with last digit equal to $last$. The answer is $\sum \limits_{m= k}^n (f(n, m, 0) + f(n, m, 1))$

However, I know it is supposed to be solved with binomial coefficients and I need the explicit answer, not a recurrence relation.

Answer 1

In our binary string with $n$ digits and $m$ ones, there will be $n-m$ $0$s. If no two $1$s can be next to each other, then we have $n-m+1$ slots to put our $m$ $1$s in. One slot is before the entire string, and another slot after each $0$. Now we have $n-m+1$ places to place $m$ $1$s, so the number of ways to do this is $n-m+1 \choose m$.

We need all the binary strings with at least $k$ $1$s here, so now we just take the sum. $$\sum_{i=k}^{\left \lceil{n/2}\right \rceil}\binom{n-i+1}{i}$$

Answer 2

Consider some fixed $k$. There are $k$ $1$'s and $n-k$ $0$'s.

Write down the $n-k$ $0$'s in a row with gaps:

$$\_0\_0\_0\_0\_0\_$$

This creates $n-k+1$ gaps (one before each $0$, one after the final $0$). Among these gaps you must place $k$ $1$'s, and there are $\binom{n-k+1}{k}$ ways to do this.

The maximum possible $k$ is going to be $\lfloor \frac{n+1}{2} \rfloor$

Overall, the number of ways to have at least $k$ non-consecutive $1$'s is:

$$S = \sum_{i=k}^{\lfloor \frac{n+1}{2} \rfloor} \binom{n-i+1}{i}$$