10
$\begingroup$

I am trying to count the number of bit-strings of length 8 with 3 consecutive zeros or 4 consecutive ones. I was able to calculate it, but I am overcounting. The correct answer is $147$, I got $148$.

I calculated it as follows:

Number of strings with 3 consecutive zeros = $2^5+5\times2^4 = 112$, because the 3 zeros can start at bit number 1, 2, 3, .., 6

Number of strings with 4 consecutive ones = $2^4+4\times2^3 = 48$, I used the same reasoning.

Now I am trying to count the number of bit-strings that contain both 3 consecutive zeros and 4 consecutive 1s. I reasoned as follows:

the strings can be of the following forms: 0001111x, 000x1111, x0001111..thus there are $2+2+2 = 6$ possibilities for bit-strings where the 3 consecutive zeros come first. Symmetrically there are $6$ bit-strings where the 4 consecutive ones come first.

Thus the answer should be = $112+48-12 = 148$.

clearly there's something wrong with my reasoning, if someone could point it out, that would be awesome. Thanks

$\endgroup$
  • 1
    $\begingroup$ Why can't the three consecutive zeros start at 7, or at 8? $\endgroup$ – Gerry Myerson Aug 4 '12 at 0:04
  • $\begingroup$ because the string can have the following forms 000xxxxx, 1000xxxx, x1000xxx, xx1000xx, xxx1000x, xxxx1000 $\endgroup$ – turingcomplete Aug 4 '12 at 0:12
  • 1
    $\begingroup$ You seem to want bit-strings of length 8, then. You've double counted the strings 00011111 and 00001111, to start, but that won't get us going in the right direction unfortunately. $\endgroup$ – Kevin Carlson Aug 4 '12 at 0:16
  • $\begingroup$ ah yes, so sorry. I will edit the question now. Thanks for pointing that out. $\endgroup$ – turingcomplete Aug 4 '12 at 0:18
  • 3
    $\begingroup$ I'm assuming you want the length to be $8$. The number of bitstrings with three consecutive zeroes is $107$; the number with four consecutive ones is $48$; the number with both is $8$; and $107 + 48 - 8 = 147$. I can't understand where your expression for the number with $3$ consecutive zeroes ($2^5 + 5 \times 2^4$) comes from at all, but I think your basic problem is overcounting strings with multiple copies of the target substring. $\endgroup$ – mjqxxxx Aug 4 '12 at 0:26
5
$\begingroup$

You've left out accounting for strings that have two triple zeroes. So $00010000,00010001,00001000,00011000,10001000$ were added to your total twice. This didn't cause any problems in your count of strings with four $1$s, however, since we can't put four $1$s in two separated places in an $8$-bit string. So the union now has $155$ elements, and cutting out the two duplicates from each symmetry of your intersection calculation turns that to $8$, for a total $107+48-8=147$.

$\endgroup$
  • $\begingroup$ Aha, I see. I missed those duplicates. Thanks, now I understand it. $\endgroup$ – turingcomplete Aug 4 '12 at 1:09
14
$\begingroup$

Here's one way to get the 107 and the 48 in the comment by mjqxxxx.

Let $a_n$ be the number of bit-strings of length $n$ with 3 consecutive zeros. Then $$a_n=2a_{n-1}+2^{n-4}-a_{n-4}$$ because you can get such a string from a such a string of length $n-1$ by putting a zero or a one at the end, or from a string of length $n-4$ with no 3 consecutive zeros by tacking 1000 on at the end. Clearly $a_0=a_1=a_2=0$ and $a_3=1$, and then you can use the recursion to find $a_4=3$, $a_5=8$, $a_6=20$, $a_7=47$, $a_8=107$.

For bit-strings with 4 consecutive ones, the same logic gets you to $$b_n=2b_{n-1}+2^{n-5}-b_{n-5}$$ and then you proceed as before.

$\endgroup$
  • $\begingroup$ This is another nice way to think about it, I did not think of that. Thank you. $\endgroup$ – turingcomplete Aug 4 '12 at 1:12
  • $\begingroup$ @Garry Myseron can you please explain how you got above recurrences? How to further modify them based on change in question? $\endgroup$ – mcjoshi Dec 15 '16 at 15:13
  • 1
    $\begingroup$ @thor, the sentence after the first recurrence explains how I got that recurrence. The second one follows the same logic, but with 4 everywhere instead of three. How to modify them depends on exactly what the change is in the question. Why not post a new question, and probably someone will answer, instead of tacking this on as a comment on a question from four years ago? $\endgroup$ – Gerry Myerson Dec 16 '16 at 4:01
3
$\begingroup$

$ \begin{array}{|l|r|l|} \hline format & N & exceptions \\ \hline 000***** & 32 & \\ 1000**** & 16 & \\ *1000*** & 16 & \\ **1000** & 16 & \\ ***1000* & 14 & 0001000* \\ ****1000 & 13 & 000*1000 , 10001000 \\ 1111**** & 13 & 1111000* , 11111000 \\ 01111*** & 7 & 01111000 \\ *01111** & 8 & \\ **01111* & 6 & 0001111* \\ ***01111 & 6 & *0001111 \\ \hline \end{array}$

Total: $147$

$\endgroup$
2
$\begingroup$

Let $n$ be a nonnegative integer. Let $a_n$ be the number of bit strings of length $n$ with at least 3 consecutive zeros. Clearly $a_0 = 0$, $a_1 = 0$, $a_2 = 0.$ Let $n \geq 3.$ Denote by $S$ the set of all bit strings of length $n$ with at least 3 consecutive zeros. The set $S$ is a disjoint union of the following four sets:

  • $S_3$ the set of all bit strings of length $n$ that end with $000$,
  • $S_2$ the set of all bit strings in $S$ that end with $100$,
  • $S_1$ the set of all bit strings in $S$ that end with $10$,
  • $S_0$ the set of all bit strings in $S$ that end with $1$.

These sets have the following cardinalities: $|S_3| = 2^{n-3}$, $|S_2| = a_{n-3}$, $|S_1| = a_{n-2}$, $|S_0| = a_{n-1}$. Since $|S| =a_n$, by the sum rule $$ a_n = 2^{n-3} + a_{n-3} + a_{n-2} + a_{n-1}. $$ Since $a_0 = 0$, $a_1 = 0$, $a_2 = 0$, we have \begin{align*} a_3 & = 2^0 + 0 + 0 + 0 = 1\\ a_4 & = 2^1 + 0 + 0 + 1 = 3\\ a_5 & = 2^2 + 0 + 1 + 3 = 8\\ a_6 & = 2^3 + 1 + 3 + 8 = 20\\ a_7 & = 2^4 + 3 + 8 + 20 = 47\\ a_8 & = 2^5 + 8 + 20 + 47 = 107. \end{align*}

For bit strings with at least 4 consecutive ones, the same reasoning leads to the recursion $$ b_0 = b_1 = b_2 = b_3 = 0, \quad b_n=2^{n-4}+b_{n-4}+ b_{n-3}+ b_{n-2}+ b_{n-1}, \ n\geq 4. $$

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