How many words of length $n$ can we make from $0, 1, 2$ if $2$'s cannot be consecutive?

Question

How many words we can make from $0,1,2$? The restriction is we can't put the digit $2$ after the digit $2$.

My solution:

I tried to solve it with Inclusion-Exclusion Principle. Count the number of the words without restriction and then I decreased the options that I don't want. The number of ways to make words without restriction $3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot \ldots \cdot 3$, so this is $3^n$. And then the number that I don't want to count is: $$\binom {n-1}{2} - \binom {n-2}{3} + \cdots + (-1)^n \cdot \frac{ (n-(n+1)}{(i+1)!}$$ so my solution is $$3^n - \sum_{i=1}^n-1 \frac{(-1)^n \cdot (n-i)}{(i+1)!}$$ This is not the answer. Can someone help me? What did I do wrong? Does the problem have any solution with a recurrence relation??

Thanks for your help!

Answer 1

This problem is best approached through a recurrence relation.

Let $a_n$ denote the number of permissible sequences of length $n$.

No sequence of length $1$ can have two consecutive $2$'s. Since there are three ways the first position can be filled, $a_1 = 3$.

The only sequence of length $2$ that has two consecutive $2$'s is $22$. Since each of the two positions can be filled in two ways, $a_2 = 3 \cdot 3 - 1 = 8$.

Notice that any permissible sequence of length $n$ can be extended to a sequence of length $n + 1$ by appending a $0$ or a $1$ to the end of the permissible sequence of length $n$.

We can only have a permissible sequence of length $n + 1$ that ends in a $2$ if the $n$th digit is a $0$ or a $1$. Hence, any permissible sequence of length $n - 1$ can be extended to a permissible sequence of length $n + 1$ by appending $02$ or $12$ to the end of the permissible sequence of length $n - 1$.

Hence, we have the recurrence relation \begin{align*} a_1 & = 3\\ a_2 & = 8\\ a_{n + 1} & = 2a_n + 2a_{n - 1}, n \geq 2 \end{align*}

If I am interpreting your attempt correctly, you are trying to eliminate those sequences with two or more consecutive $2$'s. However, you have only excluded those sequences in which all the $2$'s are consecutive. They can also appear in disjoint pairs. For instance, both the sequences $12220$ and $22122$ have two pairs of consecutive $2$'s. The consecutive pairs overlap in $12220$ and are disjoint in $22122$. Trying to count pairs of consecutive $2$'s becomes trickier as $n$ increases, which is why I approached the problem through a recurrence relation.

Answer 2

Forgive the second answer, but I can't comment on the previous answer (not yet enough reputation). The recurrence in N.F. Taussig's answer is correct (and very concisely explained!). I would add you can get a closed form, since this is a linear recurrence. In this case it's very nice (see http://mathworld.wolfram.com/LinearRecurrenceEquation.html).

Any permissible sequence of length $n$ can be extended to a permissible sequence of length $n+1$ by appending a $0$ or a $1$ (there's the $2a_n$). A permissible sequence of length $n+1$ that ends in a $2$ must be obtained from a permissible sequence of length $n-1$ by appending either $02$ or $12$ (not $01$ or $02$, and there's the $2a_{n-1}$).

Either way, the recurrence relation is certainly $$a_{n+1}=2a_n+2a_{n-1},n\ge 2.$$

Answer 3

This answer is based upon the Goulden-Jackson Cluster Method which is a convenient method to derive a generating function for problems of this kind.

We consider words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{0,1,2\}$$ and the set $\mathcal{B}=\{22\}$ of bad words, which are not allowed to be part of the words we are looking for.

We derive a function $F(x)$ with the coefficient of $x^n$ being the number of wanted words of length $n$. According to the paper (p.7) the generating function $F(x)$ is \begin{align*} F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})} \end{align*} with $d=|\mathcal{V}|=3$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[22]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[22])&=-x^2-\text{weight}(\mathcal{C}[22])x \end{align*} and get \begin{align*} \text{weight}(\mathcal{C}[22])=-\frac{x^2}{1+x} \end{align*}

It follows:

A generating function $F(x)$ for the number of words built from $\{0,1,2\}$ which do not contain the subword $22$ is \begin{align*} F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\left(1-3x+\frac{x^2}{1+x}\right)^{-1}\\ &=\frac{1+x}{1-2x-2x^2}\\ &=1+3x+8x^2+\color{blue}{22}x^\color{blue}{3}+60x^4+164x^5+448x^6\\ &\qquad+1224x^7+3344x^8+9136x^9+\cdots\tag{1} \end{align*}

We see e.g. the term $22x^3$ indicates there are $\color{blue}{22}$ different words of length $\color{blue}{\text{three}}$ built from $\{0,1,2\}$ which do not contain $22$. Out of the $3^3=27$ different words of length three built from $\{0,1,2\}$ there are precisely five words \begin{align*} 022,122,222,221,220 \end{align*} which are to exclude, resulting in a total of $27-5=22$ words.

Using partial fraction decomposition we can derive a representation of $F(x)$ as geometric series expansion. From this representation we can easily obtain the coeffcients of $x^n$ which are the number of wanted words, i.e. the words which do not contain $22$.

We obtain \begin{align*} F(x)&=\frac{1+x}{1-2x-2x^2}\\ &=\frac{2+\sqrt{3}}{2\sqrt{3}}\cdot\frac{1}{1-(1+\sqrt{3}x)}-\frac{2-\sqrt{3}}{2\sqrt{3}}\cdot\frac{1}{1-(1-\sqrt{3}x)}\\ &=\frac{2+\sqrt{3}}{2\sqrt{3}}\sum_{n=0}^\infty(1+\sqrt{3})^nx^n-\frac{2-\sqrt{3}}{2\sqrt{3}}\sum_{n=0}^\infty(1-\sqrt{3})^nx^n\\ \end{align*} and conclude:

The number of words of length $n$ built from $\{0,1,2\}$ which do not contain $22$ is \begin{align*} \frac{2+\sqrt{3}}{2\sqrt{3}}(1+\sqrt{3})^n-\frac{2-\sqrt{3}}{2\sqrt{3}}(1-\sqrt{3})^n\qquad\qquad n\geq 0 \end{align*} which is a sequence starting with \begin{align*} 1,3,8,22,60,164,448,1224,3344,9136,\ldots \end{align*} in accordance with (1).