[Math] 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.

combinatoricsdiscrete mathematics

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?

Best Answer

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.

Related Question