A letter sequence problem

Question

If I have an $8$ letter string of the letters $C$ and $N$, how many ways can I arrange the letters so that no two N's are adjacent to each other?

Answer 1

Here we derive a recurrence relation. We consider words of length $n$ built from an alphabet $\{C,N\}$ and denote the number of valid words with $a_n$.

We obtain a recurrence relation for $a_{n+1}$ by partitioning valid words of length $n+1$ into two disjoint sets.

• Termination with $C$: A word of length $n+1$ may end with the letter $C$. In this case we have $a_n$ possibilities to fill the left-most $n$ positions with valid words.
• Termination with $N$: If on the other hand the word terminates with $N$ it terminates in fact with $CN$, since $NN$ is not admissible. We have therefore $a_{n-1}$ possibilities to fill the $n-1$ left-most positions with valid words of length $n-1$. We obtain the recurrence relation \begin{align*} \color{blue}{a_{n+1}=a_n+a_{n-1}\qquad\qquad n\geq 1} \end{align*} It is easy to determine the initial conditions, since the valid words of length $n=1$ are $\{C,N\}$ and $n=2$ are $\{CC,CN,NC\}$, so that $\color{blue}{a_1=2}$ and $\color{blue}{a_2=3}$.

We finally get Fibonacci-numbers $a_n$: \begin{align*} \begin{array}{r|rrrrrrrr} n&1&2&3&4&5&6&7&8\\ a_n&2&3&5&8&13&21&34&\color{blue}{55}\\ \end{array} \end{align*} and conclude there are $\color{blue}{a_8=55}$ valid words of length $8$.