Counting number of strings which contain two $a$'s which are not next to each other

Question

Here is the question

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 ≥ 4$?

The four possible answers are

a) $S_n = \binom{n}{2}$

b) $S_n =\binom{n}{2} - n - 1$

c) $S_n = \binom{n}{2} - n$

d) $S_n = \binom{n}{2} - n + 1$

I got $b)$ for my answer by converting $a$ to $0$ and $b$ to $1$ then writing out all possible bit strings. Why is the answer $d)$ in this case?

Answer 1

There are $\binom{n}{2}$ ways to choose the two positions for the $a$'s. Of these, $n-1$ pairs are next to each other ($\{1,2\}, \{2,3\},\ldots\{n-1,n\}$) so these have to be discarded. We are left with $\binom{n}{2} - (n-1)$ options, which indeed is answer $d$.

Answer 2

Note that $$\overbrace{\underbrace{\dots}_{x_1}a\underbrace{\dots}_{x_2+1}a\underbrace{\dots}_{x_3}}^{n}.$$ Hence we have to count the non-negative integer solutions of $$x_1+x_2+1+x_3=n-2.$$ Then use Stars and bars: $\binom{n-1}{2}=\binom{n}{2}-\binom{n-1}{1}=\binom{n}{2}-(n-1)$.