Question: 2016 Fall Final - 7
Consider strings of characters, each character being $a$ or $b$, that contain exactly two $a$'s and
these two $a$'s are not next to each other. Let $S_n$ be the number of such strings having length
$n$. Which of the following is true for $n \geq 4$?
(a)
$S_n = {n \choose 2}$
(b)
$S_n = {n \choose 2} - n$
(c)
$S_n = {n \choose 2} - n + 1$
(d)
$S_n = {n \choose 2} - n - 1$