2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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$? $\endgroup$ – BillyJoe Dec 12 '20 at 18:08
  • $\begingroup$ Yes is there a closed-form solution to this type of thing? $\endgroup$ – skyfire Dec 12 '20 at 18:10
  • $\begingroup$ Take for example the string $011100111$ and $m=3$, is $0111$ to be counted twice or once? $\endgroup$ – BillyJoe Dec 12 '20 at 18:30
  • $\begingroup$ Just once. so 011100000, 000000111 and 011100111 would be considered distinct from one another. $\endgroup$ – skyfire Dec 12 '20 at 18:37
  • $\begingroup$ 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. $\endgroup$ – skyfire Dec 12 '20 at 18:43
2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Still working through this gimme a minute to verify $\endgroup$ – skyfire Dec 12 '20 at 21:44
  • $\begingroup$ Awesome works as expected. Thank you! Not sure why I was unable to get Ross's answer to work. $\endgroup$ – skyfire Dec 12 '20 at 22:03
  • $\begingroup$ even works below $m=8$, but probably should reiterate the caveat that $n>=m/2$ is required $\endgroup$ – skyfire Dec 12 '20 at 22:08
  • 1
    $\begingroup$ I think it does not have the restriction $n \ge m/2$. $\endgroup$ – BillyJoe Dec 12 '20 at 22:31
  • $\begingroup$ 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. $\endgroup$ – skyfire Dec 13 '20 at 6:23
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ $T(m,n) \rightarrow T(m,i)$. $\endgroup$ – BillyJoe Dec 12 '20 at 20:33
  • $\begingroup$ 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$. $\endgroup$ – skyfire Dec 12 '20 at 20:49
  • $\begingroup$ I found an off by $1$ error. Now it gives $28,12,5,2,1$ for a total of $48$ $\endgroup$ – Ross Millikan Dec 13 '20 at 0:54
  • $\begingroup$ @BillyJoe: Correct. Thanks. Somehow I missed your comment earlier. $\endgroup$ – Ross Millikan Dec 13 '20 at 3:47
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.