Number of possible bit sequences of length m with at least n consecutive 1's in them

Question

I have seen similar questions to this but they each seem to be special cases of this general question. Answering this would be beneficial to my research, but I am not a combinatorics expert, and this seemingly simple question eludes me. Is there a simple formula to calculate this? Everything I have seen online has been centered around things like "either 2 consecutive 1's or 0's" or "contains no ..".

If it helps, I know that for $m = 8$ bits and say the sequence is denoted $S(m,n)$ $$ S(m = 8, n = 1) = 255 \\ S(8,2) = 201 \\ S(8,3) = 107 \\ S(8,4) = 48 \\ S(8,5) = 20 \\ S(8,6) = 8 \\ S(8,7) = 3 \\ S(8,8) = 1 $$

Interestingly I'm finding that $S(8,4)=S(9,5)=S(10,6)=S(11,7)=48$ I haven't tested $S(12,8)$ because I don't want my computer to melt but I'm seeing a pattern... However this does not seem to work for $m<8$.

Answer 1

Thanks to @Ross Millikan formula, which I searched with Approach Zero, I could find this answer, and using again Approach Zero with that result, this other beautiful answer. Both give the complementary result, so in your case we have:

$$S(m,n) = 2^m-\sum_{q=0}^{\lfloor m/n\rfloor} {m-nq\choose q} (-1)^q 2^{m-(n+1)q} + \sum_{q=0}^{\lfloor m/n\rfloor - 1} {m-n(q+1)\choose q} (-1)^q 2^{m-n-(n+1)q}$$

See the links for details.

Answer 2

If the string is $m$ bits long and you demand a run of exactly $n\ 1$s we can find a formula for $n \ge \frac m2$. Let us call this $T(m,n)$. If the run is at one end of the string ($2$ choices) you need a $0$ at the end of the run and have $2^{m-n-1}$ choices for the other bits. If the run is not at the end of the string, there are $m-n-1$ places it can start and you have $2^{m-n-2}$ choices to complete the string. If $m-n-2$ is negative there are no other bits to fill in. So $$T(m,n)=\begin {cases} 1&n=m\\2&n+1=m\\2^{m-n}+(m-n-1)2^{m-n-2}&n+2 \le m \end {cases} $$ and the fact that it only depends on $m-n$ is clear. Then $$S(m,n)=\sum_{i=n}^mT(m,i)$$ I repeat that this only works for $n \ge \frac m2$. The reason it only depends on $m-n$ is because if you take a string of the type $(m,n)$ you can find a unique string of type $(m+1,n+1)$ by extending the run by one more bit.

Answer 3

I will not give a formula, but just a recurrence relation. Let T(m, n) be the number of strings of length m with a run of n consecutive 1's.

Consider all the strings of length m-1. Exactly T(m-1, n) of them already contain a string of 'n' consecutive digits. Since we can add a 0 or a 1 we will get double this amount of length m strings strings.

However adding a 1 in the m'th place will give a new good string if the last (n-1) digits are a 1 and the n'th to last digit is a 0 and in addition the digits in place 1, ..., m - n - 1 do not contain a run of n consecutive 1's. i.e. the string looks like this: $$ \underbrace{xx..xx}_{m - n - 1}0\underbrace{11..11}_{n - 1} $$ There are 2^{m - n - 1} possibilities for the x-digits, but we should exclude T(m - n - 1, n) of them to avoid the double counting.

Adding it all up we find $$ T(m, n) = 2\cdot T(m - 1, n) - T(m - n - 1, n) + 2^{(m - n - 1)} $$

If $m - n - 1 \leq n$, i.e. $m \leq 2n + 1$, the $T(m - n - 1, n)$ term vanishes and you should be able to solve the recurrence relation.