Solution: 2022 Winter Final - 3

Author: Michiel Smid

Question

Consider strings of length $70$, in which each character is one of the characters $a,b,c,d,e$. How many such strings have exactly $5$ letters $a$ or exactly $15$ letters $b$?

(a)

$\binom{70}{5}\cdot 4^{65} + \binom{70}{15}\cdot 4^{55}$

(b)

None of the above

(c)

$\binom{70}{5}\cdot 4^{65} + \binom{65}{15}\cdot 4^{50} $

(d)

$\binom{70}{5}\cdot 4^{65} + \binom{65}{15}\cdot 4^{50} - \binom{70}{5}\cdot\binom{65}{15}\cdot 3^{50}$

(e)

$\binom{70}{5}\cdot 4^{65} + \binom{70}{15}\cdot 4^{55} - \binom{70}{5}\cdot\binom{65}{15}\cdot 3^{50}$

Solution

Let’s tear it apart

Let A be the set of all strings with exactly 5 letters $a$
We choose 5 positions out of the 70 positions to place $a$'s: $ \binom{70}{5} $
Each of the remaining 65 positions can be any of the 4 other letters: $ 4^{65} $
$ |A| = \binom{70}{5} \cdot 4^{65} $
Let B be the set of all strings with exactly 15 letters $b$
We choose 15 positions out of the 70 positions to place $b$'s: $ \binom{70}{15} $
Each of the remaining 55 positions can be any of the 4 other letters: $ 4^{55} $
$ |B| = \binom{70}{15} \cdot 4^{55} $
Let's determine $A \cap B$
We choose 5 positions out of the 70 positions to place $a$'s: $ \binom{70}{5} $
We choose 15 positions out of the remaining 65 positions to place $b$'s: $ \binom{65}{15} $
Each of the remaining 50 positions can be any of the 3 other letters: $ 3^{50} $
$ |A \cap B| = \binom{70}{5} \cdot \binom{65}{15} \cdot 3^{50} $

Now, let’s get this bread

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

$ |A \cup B| = \binom{70}{5} \cdot 4^{65} + \binom{70}{15} \cdot 4^{55} - \binom{70}{5} \cdot \binom{65}{15} \cdot 3^{50} $