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

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$$.

• Is the original $m$-bit string arbitrary? In other words, do we need to sum the number of all possible subsequences of all possible strings of length $m$? – BillyJoe Dec 12 '20 at 18:08
• Yes is there a closed-form solution to this type of thing? – skyfire Dec 12 '20 at 18:10
• Take for example the string $011100111$ and $m=3$, is $0111$ to be counted twice or once? – BillyJoe Dec 12 '20 at 18:30
• Just once. so 011100000, 000000111 and 011100111 would be considered distinct from one another. – skyfire Dec 12 '20 at 18:37
• Really what I want to know is how many hexadecimal numbers (8 bits) contain runs of 4 bits (no wrapping around) I know the answer is 48 (for 1 byte) but I wanted to generalize. – skyfire Dec 12 '20 at 18:43

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}$$

• Still working through this gimme a minute to verify – skyfire Dec 12 '20 at 21:44
• Awesome works as expected. Thank you! Not sure why I was unable to get Ross's answer to work. – skyfire Dec 12 '20 at 22:03
• even works below $m=8$, but probably should reiterate the caveat that $n>=m/2$ is required – skyfire Dec 12 '20 at 22:08
• I think it does not have the restriction $n \ge m/2$. – BillyJoe Dec 12 '20 at 22:31
• I'll follow up in the morning but I recall testing one of the cases where n<m/2 that did not work. Think it was around m=6 and n = 2 or something. – skyfire Dec 13 '20 at 6:23

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.

• $T(m,n) \rightarrow T(m,i)$. – BillyJoe Dec 12 '20 at 20:33
• I'm testing this but I'm not getting the correct results. Maybe you can show me where I go wrong. Try $S(8,4)$, we have for $n<=m-2$ the following results ($4<=i<=6$), -> ${24, 10, 4}$. Then for $i=m-1$ we have $2$, and then $1$ for $i=m$. This leaves a sum of ${24, 10, 4, 2, 1}$ which is $41$. Not $48$. – skyfire Dec 12 '20 at 20:49
• I found an off by $1$ error. Now it gives $28,12,5,2,1$ for a total of $48$ – Ross Millikan Dec 13 '20 at 0:54
• @BillyJoe: Correct. Thanks. Somehow I missed your comment earlier. – Ross Millikan Dec 13 '20 at 3:47

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.