Solution: 2017 Winter Midterm - 4

Author: Michiel Smid

Question

Let $n \geq 13$ be an integer. What is the number of bitstrings of length $n$ that have exactly seven 0's or exactly five 1's?

(a)

${n \choose 7} + {n \choose 5}$

(b)

${n \choose 12} \cdot {12 \choose 7}$

(c)

${n \choose 7} + {n \choose 5} - {n \choose 5} \cdot {n - 5 \choose 7}$

(d)

None of the above.

We can break this down into 3 cases:

A = bitstrings of length $ n $ that have exactly seven 0's
We choose 7 positions from the $ n $ positions to place the 0's: $ \binom{n}{7} $
B = bitstrings of length $ n $ that have exactly five 1's
We choose 5 positions from the $ n $ positions to place the 1's: $ \binom{n}{5} $
$A \cap B$
There is no intersection because you cannot have seven 0s and give 1's. That's 12 bits. The thirteenth bit needs to be a 1 or 0, which breaks the rule: 0

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

$ |A \cup B| = \binom{n}{7} + \binom{n}{5} - 0 $

Thus, the number of bitstrings of length $ n $ that have exactly seven 0’s or exactly five 1’s is: $ \binom{n}{7} + \binom{n}{5} - 0$