Solution: 2016 Fall Final - 7

Author: Michiel Smid

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 \geq 4$?

(a)

$S_n = {n \choose 2} - n + 1$

(b)

$S_n = {n \choose 2} - n - 1$

(c)

$S_n = {n \choose 2}$

(d)

$S_n = {n \choose 2} - n$

Solution

Let A be the event that there are two $a$'s
Out of n positions, choose 2 of them to be $a$'s: $ \binom{n}{2} $
Everything else is a $b$, which is only 1 option.
$ |A| = \binom{n}{2} $
Let B be the event that there are two $a$'s and they are next to each other
Out of n-1 positions, choose 1 of them to be the first $a$.
The next position is the second $a$.
Everything else is a $b$, which is only 1 option.
$ |B| = n-1 $

$S_n = |A| - |B|$

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

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