Question

How many bit strings of length 12contain

a) exactly three 1s?

b) at most three 1s?

c) at least three 1s?

d) an equal number of 0sand 1s?

Short answer

a) There are 220 bit strings of length 12 contain exactly three 1s.

b) There are 299 bit strings of length 12 contain at most three 1s.

c) There are 4017 bit strings of length 12 contain at least three 1s.

d) There are 924 bit strings of length 12 contain an equal number of 0s and 1s .

Step-by-step solution

Given data

Bit strings of length 12

Concept of Combination

A combination is a selection of items from a set that has distinct members.

Formula:

${}_{\mathbf{n}}{\mathbf{C}}_{\mathbf{r}}\mathbf{=}\frac{\mathbf{n}\mathbf{!}}{\mathbf{r}\mathbf{!}\mathbf{(}\mathbf{n}\mathbf{-}\mathbf{r}\mathbf{)}\mathbf{!}}$

Calculation for the number of bit strings for exactly four 1s

a)

To choose 3 position to 1's out of 12 :

$\begin{array}{r}\mathrm{C}(12,3)=\frac{12!}{(3!\times 9!)}\\ =\frac{(12\times 11\times 10)}{3!}\\ =220\end{array}$.

Thus, there 210 are bit strings of length 12 contain exactly three 1s .

Calculation for the number of bit strings for at most four 1s

b)

There are zero 1s, one 1s, two 1s, three 1s in the bit strings of length 12:

$\begin{array}{r}\mathrm{C}(12,0)+\mathrm{C}(12,1)+\mathrm{C}(12,2)+\mathrm{C}(12,3)=12!/(0!\times 12!)+12!/(1!\times 11!)+12!/(2!\times 10!)+12!/(3!\times 9!)\\ =1+12+66+220\\ =299\end{array}$

Thus, there are 299 bit strings of length 12 contain at most three 1s.

Calculation for the number of bit strings for at least four 1s

c)

Subtract the total number of bit strings of length 12 those that have only 0,1,2,3 or 1s :

$\begin{array}{r}{2}^{12}-\left[\mathrm{C}\right(10,0)+\mathrm{C}(10,1)+\mathrm{C}(10,2\left)\right]=4096-1-12-66\\ =4017\end{array}$

Thus, there are 4017 bit strings of length 12 contain at least three 1s.

Calculation for the number of bit strings for an equal number 0s and 1s

d)

To choose 6 out of 12 position to place :

$\begin{array}{r}C(12,6)=\frac{12!}{(6!\times 6!)}\\ =924\end{array}$

Thus, there are 924 bit strings of length 12 contain an equal number of 0s and 1s .