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

Question

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.

Answer 1

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

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

Answer 2

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.