Practice By Tag: The Principle of Inclusion and Exclusion

Question: 2016 Fall Midterm - 6

1 . Let $n \geq 5$ and consider strings of length $n$ consisting of the characters $a$, $b$, $c$, and $d$. How many such strings are there that start with $ad$ or end with $dcb$?

(a)

$4^{n - 2} + 4^{n - 3}$

(b)

$4^{n - 2} + 4^{n - 3} - 4^{n - 5}$

(c)

$4^n - 4^{n - 5}$

(d)

$4^n - 4^{n - 2} - 4^{n - 3}$