Solution: 2018 Fall Final - 3

Author: Michiel Smid

Question

Consider strings of length 70, in which each character is one of the letters $a, b, c$. How many such strings have exactly 12 letters $c$ or exactly 30 letters $b$?

(a)

None of the above.

(b)

${70 \choose 12} + {70 \choose 30} - {58 \choose 30}$

(c)

${70 \choose 12} \cdot 2^{58} + {70 \choose 30} \cdot 2^{40} - {70 \choose 12} \cdot {58 \choose 30}$

(d)

${70 \choose 12} \cdot 2^{58} + {70 \choose 30} \cdot 2^{40}$

Solution

Let C be the event that the string has exactly 12 letters $c$
First, we choose 12 positions out of the 70 for the letter $c$: $ \binom{70}{12} $
Then, we choose the positions of the letters $a$ and $b$ for the remaining 58 positions: $ 2^{58} $
$ |C| = \binom{70}{12} \cdot 2^{58} $
Let B be the event that the string has exactly 30 letters $b$
First, we choose 30 positions out of the 70 for the letter $b$: $ \binom{70}{30} $
Then, we choose the positions of the letters $a$ and $c$ for the remaining 40 positions: $ 2^{40} $
$ |B| = \binom{70}{30} \cdot 2^{40} $
Let's determine $ B \cap C $
First, we choose 12 positions out of the 70 for the letter $c$: $ \binom{70}{12} $
Then, we choose 30 positions out of the remaining 58 for the letter $b$: $ \binom{58}{30} $
The remaining 28 positions are for the letter $a$: 1
$ |B \cap C| = \binom{70}{12} \cdot \binom{58}{30} $

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

$ |B \cup C| = \binom{70}{30} \cdot 2^{40} + \binom{70}{12} \cdot 2^{58} - \binom{70}{12} \cdot \binom{58}{30} $