0
$\begingroup$

How many different bit strings of length $10$ contain exactly five $1$s or begin with a $0$?

My work

$2^4 + 2^4 + 2^4 + 2^4 + 2^4 + 2^5 + 2^9$

Reason:

First will be $0$, so there will be $2^9$ ways and it continues.

$\endgroup$
1
  • 1
    $\begingroup$ You should explain your reasoning. $\endgroup$ – N. F. Taussig Apr 25 '18 at 0:38
1
$\begingroup$

Let $A$ be the set of bit strings of length $10$ that contain exactly five $1$s; let $B$ be the set of bit strings of length $10$ that begin with $0$. We wish to calculate $|A \cup B|$, the number of bit strings of length $10$ that contain exactly five $1$s or begin with a $0$.

Venn_diagram_for_two_sets

If we simply add $|A|$, the number of bit strings of length $10$ that contain exactly five $1$s, and $|B|$, the number of bit strings of length $10$ that begin with a $0$, we will have counted those bit strings in $A \cap B$, the set of bit strings of length $10$ that have exactly five ones and begin with a $0$, twice - once when we count bit strings of length $10$ that contain exactly five $1$s and once when we count bit strings of length $10$ that begin with a $0$. We only want to count them once. Hence, we must subtract $|A \cap B|$ from $|A| + |B|$ to find $|A \cup B|$.

$$|A \cup B| = |A| + |B| - |A \cap B|$$

$|A|$: The number of bit strings with exactly five $1$s is $$\binom{10}{5}$$ since we must choose which five of the ten positions will be filled with $1$s.

$|B|$: The number of bit strings that begin with $0$ is $2^9$, as you found, since the first position is determined and each of the last nine positions may be filled with either a $0$ or $1$.

$|A \cap B|$: Since the first position must be filled with a $0$, five of the remaining nine positions must be filled with $1$s. These positions may be chosen in $$\binom{9}{5}$$ ways.

Hence, $$|A \cup B| = |A| + |B| - |A \cap B| = \binom{10}{5} + 2^9 - \binom{9}{5}$$

Alternate Method: We have shown that there are $2^9$ bit strings of length $10$ that begin with a $0$. These include the $\binom{9}{5}$ bit strings of length $10$ that contain exactly five ones. What we have not yet counted is bit strings of length $10$ that begin with a $1$ and contain exactly five $1$s. Such bit strings have exactly four $1$s among the last nine positions, so there are $\binom{9}{4}$ of them. Hence, the number of bit strings of length $10$ that have exactly five $1$s or begin with a $0$ is $$2^9 + \binom{9}{4}$$

$\endgroup$
2
  • $\begingroup$ can you please explain why did you subtract $C(9,5)$ $\endgroup$ – tien lee Apr 25 '18 at 0:55
  • $\begingroup$ We counted bit strings that begin with a $0$ and have exactly five $1$s once when we count those bit strings that begin with a $0$ and a second time when we count those bit strings that have exactly five $1$s. However, we only want to count those bit strings once, so we must subtract that satisfy both conditions from the total. $\endgroup$ – N. F. Taussig Apr 25 '18 at 0:58
0
$\begingroup$

Let $A$ be the set of strings containing fives $1$'s, and let $B$ be the set of strings starting with $0$. You want to count $|A\cup B|$. In this case, a good way to do it is via $$ |A\cup B|=|A|+|B|-|A\cap B| $$ Note that $|A\cap B|$ is easier to count; it is the number of strings starting with a $0$ and having five $1$'s. Simply choose which of the nine bits are equal to $1$ in $\binom95$ ways, and you have chosen your string.

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