# Find a recurrence relation and initial values for W(n), the number of words of length n from alphabet {a,b,c} with no adjacent a's.

Find a recurrence relation and initial values for W(n), the number of words of length n from alphabet {a,b,c} with no adjacent a's.

This is a problem from How to Count: An Introduction to Combinatorics and Its Applications by Beeler, exercise 1.6.7. Of course, W(1) = 3 since the possibilities are {a},{b},{c}, and W(2) = 8. Then I can solve for W(3) by accounting for the total number of combinations, $3^3$, then subtracting cases of adjacent a's, totaling to 9 cases, which gives the result of 18.

Will the Principle of Inclusion/Exclusion somehow aid me with this?

Call a sequence with no two adjacent a's good. A good sequence either (i) ends with b or c or (ii) ends with a.

The Type (i) good sequences of length $n$ are obtained by appending b or c to a good sequence of length $n-1$. So there are $2W(n-1)$ Type (i) good sequences of length $n$.

The Type (ii) good sequences of length $n\ge 2$ are obtained by appending an a to a good sequence of length $n-1$ that doesn't end in a. Such a good sequence is obtained by appending b or c to a good sequence of length $n-2$, so there are $2W(n-2)$ of them.

It follows that for $n\ge 2$, $$W(n)=2W(n-1)+2W(n-2).$$ As initial conditions we can use $W(0)=1$. $W(1)=3$.

Remark: It might be interesting to attempt to use Inclusion/Exclusion to find an expression for $W(n)$. Doable, but we end up with a messy sum.

The recurrence we found is by no means the only possible one. However, it is a linear homogeneous recurrence with constant coefficients, so it can be solved using standard tools.

First we will find the number of words having $t$ letters $b$ and $c$, there is $2^t$ ways to choose the order of this letters, no we will use the method of stars and bars, we will write the $t$ letters in row and lat a gap between every two mletters: $$x\ \ \ \ \ \ \ \ x\ \ \ \ \ \ \ \ x\ \ \ \ \ \cdots\cdots \ \ \ x\ \ \ \ \ \ \ \ x\ \ \ \ \ \ \ \ x\ \ \ \ \ \ \ \ x\ \ \ \ \ \ \ \ x\ \ \ \ \ \ \ \$$

we have $t+1$ gaps and in each gap we can decide to write an $a$ in it or not, hence we have ${t+1 \choose n-t}$ ways of choosing the $a$'s in the word , finally we have:

$$W(n)=\sum_{t\leq 2t+1,t\leq n}{t+1 \choose n-t}2^t=\sum_{x=0}^{\lfloor \frac{n+1}{2}\rfloor}{n-x+1 \choose x}2^{n-x}$$