[Math] Number of Bit Strings with Five Zeros

combinatoricsdiscrete mathematics

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

Best Answer

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

Related Solutions

[Math] Number of bit strings with 3 consecutive zeros or 4 consecutive 1s

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.

[Math] bit string question

6 types for five $0$'s:

XXXX100000
XXX100000X
XX100000XX
X100000XXX
100000XXXX
00000XXXXX

$5 \cdot 2^4 + 2^5 = 112$

7 types for four $1$'s:

XXXXX01111  !!! 1 repeat with (1) and 2 with (2)
XXXX01111X  !!! 2 repeats with (2)
XXX01111XX
XX01111XXX
X01111XXXX
01111XXXXX  !!! (1)
1111XXXXXX  !!! (2)

$6 \cdot 2^5 + 2^6 - 5 = 251$

They intersect in 8 obvious cases, so the answer is $112 + 251 - 8 = 355$

Best Answer

Related Solutions

[Math] Number of bit strings with 3 consecutive zeros or 4 consecutive 1s

[Math] bit string question

Related Question