Solution: 2018 Winter Midterm - 3

Author: Michiel Smid

Question

Consider strings consisting of 12 characters, where each character is an element of the set $\{a,b,c,d,e\}$. The positions in such strings are numbered as $1,2,3,\dots,12$.
How many such strings contain at least two $a$'s?

(a)

$5^{12} - 4^{12} - 12 \cdot 4^{11}$

(b)

$12^{5} - 12^{4} - 12 \cdot 12^{4}$

(c)

$5^{12} - 4^{12} - 12 \cdot 4^{12}$

(d)

$12^{5} - 12^{4} - 12 \cdot 11^{4}$

Solution

A = At least two $ a $‘s

B = No $ a $‘s

Each position has 4 choices: $ b, c, d, e $

There are 12 positions, so there are $ 4^{12} $ ways to choose the characters.

C = Exactly 1 $ a $

There are 12 positions to choose from, and 1 of them must be $ a $.

The other 11 positions can be any of the 4 characters: $ b, c, d, e $

$ |C| = 12 \cdot 4^{11} $

$ |A| = \text{All Possible Strings} - \text{No $ a $‘s} - \text{Exactly 1 $ a $} $

$ |A| = 5^{12} - 4^{12} - 12 \cdot 4^{11} $