[Math] Counting bit strings of length 10 contain either 5 consecutive 0’s or 5 consecutive 1’s

combinatorics

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

My Solution:

for 5 consecutive 0's

After we have filled 0's from $1^{st}$ position we have 2 choices each for the rest 5 positions
After we have filled 0's from $2^{nd}$ position we have 2 choices each for the rest 5 positions
$\dots$
After we have filled 0's from $6^{th}$ position we have 2 choices each for the rest 5 positions

making it total $6 \times 2^{5}$

Now, for 5 consecutive 1's

After we have filled 1's from $1^{st}$ position we have 2 choices each for the rest 5 positions
After we have filled 1's from $2^{nd}$ position we have 2 choices each for the rest 5 positions
$\dots$
After we have filled 1's from $5^{th}$ position we have 2 choices each for the rest 5 positions

making it total $4 \times 2^{5}$

Becasue 1111100000 and 0000011111 is already counted above

So making a total of $(6+4) \times 2^{5}=10 \times 2^5$

Please correct me If I've done something wrong

Best Answer

The problem with your approach is that you are counting some arrangements more than once. Eg when you count by grouping and summing, you must take care that the groups are exclusive. For example, you count:

00000***** $\to 2^5$

*00000**** $\to 2^5$

but a configuration like 0000001111 belongs to both groups, hence you are couting it twice. And some, more than twice (eg, 0000000111 belongs to three groups).

To count the strings of 10 bits with at least 5 consecutive zeros, lets group them according to $k=$ the first zero position in the (possibly larger than 5) run. Then $k\in \{1,2,3,4,5,6\}$ (counting from one).

For $k=1$, we have $2^5$ strings: ( 00000*****)

For $k>1$ , we have $2^4$ strings (eg *100000*** for $k=3$)

This groping is exhaustive and exclusive. Hence the number of strings with at least 5 consecutive zeros is $ 2^5 + 5 \times 2^4 = 112$

By symmetry, the number of strings with at least 5 consecutive ones is the same; however, this would count both 0000011111 and 1111100000 twice (as you noticed), hence the total number is

$$112 + 112 -2 = 222$$

Notice that this method only works because of $\ell \ge n/2$ ($\ell$ is the runlength, $n$ the total length) , otherwise more complicated methods would be needed (example).

Related Question