Question

How many ternary strings of length six do not contain two consecutive$\mathbf{0}\mathbf{\text{'}}\mathit{s}$or twoconsecutive$\mathbf{1}\mathbf{\text{'}}\mathit{s}$?

Short answer

There are 239 ternary strings of length six that do not contain two consecutive $0\text{'}s$or two consecutive $1\text{'}s$.

Step-by-step solution

Given data

A string that contains only $0\text{'}s$, $1\text{'}s$and $2\text{'}s$is called a ternary string.

Concept used of recurrence relation 

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing ${\mathit{F}}_{\mathbf{n}}$as some combination of ${\mathit{F}}_{\mathbf{i}}$ with $\mathit{i}\mathbf{<}\mathit{n}\mathbf{)}$.

Find the number of ternary strings

We will compute $a_2$ through $a_6$ using the recurrence relation:

$$\begin{gathered} a_2=a_1+2a_0+2=3+2·1+2=7 \\ {a}_3=a_2+2a_1+2a_0+2=7+2·3+2·1+2=17 \\ {a}_4=a_3+2a_2+2a_1+2a_0+2=17+2·7+2·3+2·1+2=41 \\ {a}_5=a_4+2a_3+2a_2+2a_1+2a_0+2=41+2·17+2·7+2·3+2·1+2=99 \\ {a}_6=a_5+2a_4+2a_3+2a_2+2a_1+2a_0+2=99+2·41+2·17+2·7+2·3+2·1+2=239 \end{gathered}$$

Thus there are 239 ternary strings of length 6 that do not contain two consecutive $0\text{'}s$or two consecutive $1\text{'}s$.