Question

How many binary sequences of length 20 are there that

(a) Start with a run of 0s—that is, a consecutive sequence of (at least) one 0—then a run of 1s, then a run of 0s, then a run of 1s, and finally finish with a run of 0s?

(b) Repeat part (a) with the constraint that each run is of length at least 2.

Answer 1

How many binary sequences of length 20 is there that:

a) Start with a run of 0 's, then a run of 1 's, then a run of 0 's, then a run of 1 's, and finish with a run of 0 's? A "run" is a consecutive sequence with at least one of the indicated characters.

b) Repeat part (a) with the constraint that each run is of length at least 2

Solution:

a) The binary sequence has a length of 20 with 0 's and 1 's in the following pattern

0_1_0_1_0_

So we have to fill the gaps with 0 's and 1 's. It is sure that the characters following 0 will be 0 s and the characters following 1 will be 1 s. So we will consider them as the same type or indistinguishable or identical objects.

We have 5 places to be filled with either \(0 \mathrm{s}\) or \(1 \mathrm{s}\). These 5 places are to be filled with 15 objects which are indistinguishable.

The number of ways of distributing \(n\) identical objects to r groups is

$$C(n+r-1, r-1)=\frac{(n+r-1) !}{n !(r-1) !}$$

\(\therefore\) The number of ways of filling 15 identical objects into 5 different groups will be

\(=C(15+5-1,5-1)\)

$$=\frac{19 !}{15 ! 4 !}$$

\(=3876\)

b) Repeat part (a) with the constraint that each run is of length at least 2

So we will have the pattern as follows

$$00_{-} 11_{-} 00_{-} 11_{-} 00_{-}$$

So here we have 100 s and 1 s to be filled into 5 groups. So just like above the number of ways of filling 10 identical objects into 5 different groups will be

\(=C(10+5-1,5-1)\)

\(=\frac{14 !}{10 ! 4 !}=1001\)