1
$\begingroup$

How many bit strings of length 10 contain either five consecutive 0's or five consecutive 1's?

I think the answer to this question is:

10!/(5!*5!), according to book-keepers rule. Since, there are 10! total permutations, with 5 zeros being indistinguishable and five ones being indistinguishable. But I'm confused about the keyword, "either". Please help, thanks. :)

$\endgroup$
  • $\begingroup$ I think you are forgetting about the "consecutive" part. $\endgroup$ – André Nicolas Nov 20 '14 at 18:17
  • $\begingroup$ Yeah. But if I do it the other way, by saying that there are really two choices for each value, then the answer comes out to be, 2^5 which is 32. And the way I did it, it comes out to be, 252. I think there is something really wrong with both of my approaches. Do you see it? $\endgroup$ – muqsitnawaz Nov 20 '14 at 18:21
2
$\begingroup$

NOTE: This answer assumes that the OP asks for the number of bit strings with EXACTLY 5 consecutive 0's or 1's. It does not work if you're looking for the number of bit strings with AT LEAST 5 consecutive 0's or 1's.


There are 10 bits, so there's a total of $2^{10}=1024$ possible cases.

Let see the case of 5 consecutive 0's. Then, we need at least a 1 in every end (if there wasn't, it would be 6 consecutive 0's). Let's see all possible arranges ($x$ is a bit whose value doesn't matter, so it could be either a 1' or a 0': $$\begin{array}{rcl} 000001xxxx&&6\text{ numbers fixed, so }2^4\text{ cases}\\ 1000001xxx&&7\text{ numbers fixed, so }2^3\text{ cases}\\ x1000001xx&&7\text{ numbers fixed, so }2^3\text{ cases}\\ xx1000001x&&7\text{ numbers fixed, so }2^3\text{ cases}\\ xxx1000001&&7\text{ numbers fixed, so }2^3\text{ cases}\\ xxxx100000&&6\text{ numbers fixed, so }2^4\text{ cases} \end{array}$$

So there's $2\cdot 2^4 + 4\cdot2^3=2^5+2^5=2^6=64$ bit strings with 5 consecutive 0's.

The case of 5 consecutive 1's is exactly the same, so there's 64 bit strings with 5 consecutive 1's.

But, note we are counting twice the cases with 5 consecutive 1's and 5 consecutive 0's: $$0000011111\qquad 1111100000$$

So we need to substract 2 (2 possible bit strings) for a total of:

$$64+64-2=126\text{ bit strings with either 5 consecutive 0's or 1's}$$

$\endgroup$
  • $\begingroup$ To get multidigit exponents, enclose them in braces, so 2^{10} gives $2^{10}$ instead of $2^10$ $\endgroup$ – Ross Millikan Nov 20 '14 at 18:31
  • 1
    $\begingroup$ because $0000010000$, $0000010001$, $0000010010$... are all valid combinations (bit words with 5 consecutive zeros) $\endgroup$ – cjferes Nov 20 '14 at 18:32
  • $\begingroup$ You are treating "bit strings" in the poster's question as "numbers". They are quite different things. $\endgroup$ – user_of_math Nov 20 '14 at 18:33
  • $\begingroup$ The question is vague enough that 0000000000 applies; it has 5 consecutive 0s. It also has more than that. Your answer doesn't count for it. $\endgroup$ – Devon Parsons Nov 20 '14 at 18:33
  • $\begingroup$ As I understand the question, the OP asks for exactly 5 consecutive 0's or 1's (so my answer). I will edit to include this assumption. $\endgroup$ – cjferes Nov 20 '14 at 18:34
1
$\begingroup$

The question, as is all too often the case, is ambiguous. Do we mean exactly $5$ consecutive $0$'s, or at least $5$? We take the at least interpretation.

How does one interpret "either $\dots$ or?" Does the string with $5$ $0$'s followed by $5$ $1$'s qualify? We will do violence to ordinary English (but not to mathematical English) by deciding that it does qualify.

We first count the strings with (at least) $5$ consecutive $0$'s.

The consecutive string could start at the leftmost bit. There are $2^5$ ways to complete.

It could start at the second bit. Then the first bit is $1$, and there are $2^4$ ways to complete.

It could start at the third bit. Then the second bit is $1$, the first bit is arbitrary, as are the last $3$, for a total of $2^4$.

Starting at the fourth, fifth, sixth each contribute another $2^4$.

The total is $112$.

We have the same number with consecutive $1$'s.

However, we have double-counted the $2$ strings that have $5$ consecutive $0$'s and $5$ consecutive $1$'s.

The total is therefore $222$. If we use the exclusive or interpretation of "either $\dots$ or" this shrinks to $220$.

$\endgroup$
  • $\begingroup$ Interesting, we got the same answer. I did it via recursion. Do you think you could get a closed formula for the number of strings of length $n$? $\endgroup$ – Jorge Fernández Hidalgo Nov 20 '14 at 18:49
  • $\begingroup$ I am not sanguine about closed form. The issue is with strings that have at least $5$ of each. Counting could be an ugly Inclusion/Exclusion. $\endgroup$ – André Nicolas Nov 20 '14 at 18:53
  • $\begingroup$ There is a closed form, but it's quite a mess. The desired number is $2^n-2t_{n+3}$, where $t_i$ is the $i$-th tetranacci number, and the tetranacci numbers are given by a recurrence that can be solved in terms of the roots of a quartic equation. See my answer, and see a closed form for the tetranacci numbers (the roots of the quartic are not written explicitly) here: mathworld.wolfram.com/TetranacciNumber.html. $\endgroup$ – Steve Kass Nov 20 '14 at 19:48
1
$\begingroup$

Lets count the strings that don't have $5$ consecutive equal bits. Call such a string a "funny string".

To do this we shall create the function $f(n)$. This function counts how many "funny strings" of length $n$ there are.

It is clear $f(1)=2,f(2)=4,f(3)=8,f(4)=16,f(5)=30$

We shall now find a recurrence:

suppose we want to count the number of funny strings of length $n$. We called this number $f(n)$ . We can classify these strings into two types:

First type: Those strings in which the last bit is different to the second to last bit. There are $f(n-1)$ of this type since removing the last bit gives us a funny string of length $n-1$. And for any funny string of length $n-1$ we can create a funny string of length $n$ by adding a digit at the end that is different to the previous last digit.

Second type: These are the strings in which the last two digits are equal. The number of funny strings of this type is equal to the number of funny strings of length $n-1$ that do not end in four consecutive bits of the same type. How many of these are there?

It is easier once again to count how many funny strings of length $n-1$ do end in $4$ equal bits. There are $f(n-5)$ of these. Why? Suppose you are given a funny string of length $n-1$ that ends in $4$ equal bits. Then you can take away those $4$ last bits and you shall get a "funny string" of length $n-5$ where the last bit is different from the 4 bits you just removed. Conversely given a "funny string" of length $n-5$ if you add 4 digits different from the last one at the end you shall get a funny string of length $n-1$ that ends in $4$ equal bits.

So there are $f(n-5)$ funny strings that end in $4$ digits of the same length, and therefore there are $f(n-1)-f(n-5)$ funny strings of length $n$ of the second type.

Therefore we get $f(n)=2f(n-1)-f(n-5)$

following up our previous table and using the recursion we get:

$f(1)=2,f(2)=4,f(3)=8,f(4)=16,f(5)=30,f(6)=58,f(7)=112,f(8)=216,f(9)=416,f(10)=802$

So there are $802$ strings of length $10$ that don't have five consecutive equal bits. Thus there are $1024-802=222$ that do.

$\endgroup$
  • $\begingroup$ This answers how many strings have $5$ consecutive equal bits. In other words the number of strings in which there exists $5$ strings that are equal. $\endgroup$ – Jorge Fernández Hidalgo Nov 20 '14 at 18:47
  • $\begingroup$ Nice recurrence calculation. $\endgroup$ – André Nicolas Nov 20 '14 at 18:55
1
$\begingroup$

Suppose you have a bit string of zeros and ones, like $1110010011111101001$. This can be described (up to complementation, or flipping every bit in the string) by the lengths of the runs of $1$s and $0$s. In other words, $1110010011111101001$ or its complement, $0001101100000010110$, can be described be the sequence of run lengths $3:2:1:2:6:1:1:2:1$. If the string has $n$ bits, these run lengths add up to $n$. Such a decomposition of $n$ into an ordered sum of positive integers is called a composition of $n$. The compositions of $n$ are in one-to-two correspondence with the length $n$ bit strings. (There are two choices for the first bit, and then the composition describes the string.)

A bit string with a run of at least $5$ of the same bit will have an associated composition that contains a number that is greater than or equal to $5$.

Therefore, the number of length $n$ bit strings with no run of $5$ zeros or ones is two times the number of compositions of $n$ using parts from $1$ to $4$.

The number of compositions of $n$ using parts from $1$ to $4$ is the $n+3$-rd "tetranacci" number. See https://oeis.org/A000078.

For $n=10$, the $n+3$-rd tetranacci number is $401$, so there are $802$ length-$10$ bit strings that do not contain a run of length at least $5$. There are $1024$ strings of length 10 in all, leaving $222$ that do contain a run of length $5$.

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