The number of sequences of length $n$ with digits in $\{0, 1, 2, 3\}$ without consecutive repeated nonzero digits

Question

Let $a_n$ be the number of sequences of length $n$ with digits in $\{0, 1, 2, 3\}$ that do not contain consecutive repeated nonzero digits. The last digit of all such sequences can be 0, 1, 2, or 3. I want o find a Recurrence relation describing $a_n$.

My attempt:

If the last digit is $0$, then the remaining $n-1$ digits can be any sequence satisfying the original condition and therefore can be chosen in $a_{n-1}$ ways. However, if the last digit is $1$, $2$, or $3$, then the $n-1$ remaining digits must have the additional condition of not ending with the last digit.

Let $b^a_n$ denote the number of strings that, in addition to the original condition, end with an $a$ with $a \in {1, 2, 3}$. It's clear that $b^1_n = b^2_n = b^3_n$, so we might just show it as $b_n$. In total, we have $a_n = a_{n-1} + 3b_{n-1}$. Then we have to express $b_n$ in terms of $a_n$, but I don't know how to proceed.

Answer 1

You have $b_n$ as the number of such sequences ending in a nonzero digit. Let $c_n$ be the number of such sequences ending in $0$. Now $a_n=b_n+c_n$ and you have already determined that $c_n=a_{n-1}$

$a_n=b_n+c_n\implies b_n=a_n-c_n$

$b_n=3c_{n-1}+2b_{n-1}$

$b_n=3a_{n-2}+2(a_{n-1}-c_{n-1})$

$b_n=3a_{n-2}+2(a_{n-1}-a_{n-2})$

$b_n=2a_{n-1}+a_{n-2}$

$a_n=b_n+c_n=3a_{n-1}+a_{n-2}$

Answer 2

Let the total number of valid sequences of length $n$ be $f_n$. Let $a_n$ be the number of sequences of length $n$ such that the last digit is $0$ and $b_n$ the number of sequences such that the last digit is not $0$. Then, the number of valid sequences of length $n$ ending in $0$ is:

$$ a_n = a_{n - 1} + b_{n - 1} $$

The number of valid sequences of length $n$ ending in a non-zero digit is:

$$ b_n = 3 a_{n - 1} + 2 b_{n - 1} = 3 a_{n - 1} + 2(a_n - a_{n - 1}) = 2a_n + a_{n - 1} $$

And so we get:

$$f_n = a_n + b_n = 3 a_n + a_{n - 1}$$

We note $a_{n + 1} = f_n$ so:

$$ f_n = 3 f_{n - 1} + f_{n - 2} $$

with $f_1 = 4$ and $f_2 = 13$.

Answer 3

Define a directed graph $G$ with node set $\{0,1,2,3\}$ and adjacency matrix $$A=\begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 \end{pmatrix}.$$ By construction, the allowed sequences correspond bijectively to walks in $G$. It is well known that the $(i,j)$ entry of $A^n$ yields the number of walks of length $n$ in $G$ from $i$ to $j$. Let $e=\begin{pmatrix}1& 1& 1& 1\end{pmatrix}^T$. We have $a_n = e^T A^{n-1} e$ for $n \ge 1$. Now note that $A$ has characteristic polynomial $(\lambda + 1)^2 (\lambda^2 - 3 \lambda - 1)$, and so the Cayley-Hamilton theorem implies that $A^2=3A+I_4$. Hence for $n \ge 3$, we have $$ a_n = e^T A^{n-1} e = e^T A^{n-3}A^2 e = e^T A^{n-3}(3A+I_4) e = e^T (3A^{n-2}+A^{n-3}) e = 3a_{n-1} + a_{n-2}.$$

Answer 4

Here is a systematic approach with a convenient notation which helps to derive recurrence relations of this kind.

We count the number $a_n$ of wanted sequences of length $n$ from the set $\mathcal{V}=\{0,1,2,3\}$, i.e. sequences of length $n$ which do not contain a bad sequence from $\mathcal{B}=\{11,22,33\}$.

We do so by partitioning them according to their matching length with the initial parts of a bad sequence. We consider \begin{align*} \color{blue}{a_n=a^{[\emptyset]}_n+a^{[1]}_n+a^{[2]}_n+a^{[3]}_n}\tag{1} \end{align*}

• The number $a^{[\emptyset]}_n$ counts the number of valid sequences of length $n$ which do not start with the rightmost character of a bad sequence from $\mathcal{B}$, i.e. that start with $\color{blue}{0}$.

• The number $a^{[1]}_n$ counts the number of valid sequences of length $n$ which do start with the rightmost character of the bad sequence $1\color{blue}{1}$, i.e. $\color{blue}{1}$.

• The number $a^{[2]}_n$ counts the number of valid sequences of length $n$ which do start with the rightmost character of the bad sequence $2\color{blue}{2}$, i.e. $\color{blue}{2}$.

• The number $a^{[3]}_n$ counts the number of valid sequences of length $n$ which do start with the rightmost character of the bad sequence $3\color{blue}{3}$, i.e. $\color{blue}{3}$.

We get a relationship between valid sequences of length $n$ with those of length $n+1$ as follows:

• If a sequence counted by $a^{[\emptyset]}_n$ is appended

  • by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$.

  • If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$.

  • If it is appended by $2$ from the left it contributes to $a^{[2]}_{n+1}$.

  • If it is appended by $3$ from the left it contributes to $a^{[3]}_{n+1}$.

• If a sequence counted by $a^{[1]}_n$ is appended

  • by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$.

  • Appending from the left by $1$ is not allowed since then we have an invalid sequence starting with $\color{blue}{11}$.

  • If it is appended by $2$ from the left it contributes to $a^{[2]}_{n+1}$.

  • If it is appended by $3$ from the left it contributes to $a^{[3]}_{n+1}$.

• If a sequence counted by $a^{[2]}_n$ is appended

  • by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$.

  • If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$.

  • Appending from the left by $2$ is not allowed since then we have an invalid sequence starting with $\color{blue}{22}$.

  • If it is appended by $3$ from the left it contributes to $a^{[3]}_{n+1}$.

• If a sequence counted by $a^{[3]}_n$ is appended

  • by $0$ from the left it contributes to $a^{[\emptyset]}_{n+1}$.

  • If it is appended by $1$ from the left it contributes to $a^{[1]}_{n+1}$.

  • If it is appended by $2$ from the left it contributes to $a^{[2]}_{n+1}$.

  • Appending from the left by $3$ is not allowed since then we have an invalid sequence starting with $\color{blue}{33}$.

This relationship can be written as \begin{align*} \color{blue}{a^{[\emptyset]}_{n+1}}& \color{blue}{=a^{[\emptyset]}_{n}+a^{[1]}_{n}+a^{[2]}_{n}+a^{[3]}_{n}}\tag{2}\\ \color{blue}{a^{[1]}_{n+1}}& \color{blue}{=a^{[\emptyset]}_n\qquad\ \ +a^{[2]}_n+a^{[3]}_n}\tag{3}\\ \color{blue}{a^{[2]}_{n+1}}& \color{blue}{=a^{[\emptyset]}_n+a^{[1]}_n\qquad\ \ +a^{[3]}_n}\tag{4}\\ \color{blue}{a^{[3]}_{n+1}}& \color{blue}{=a^{[\emptyset]}_n+a^{[1]}_n+a^{[2]}_n}\tag{5}\\ \end{align*}

We can now derive a recurrence relation from (1) - (5):

We obtain for $n\geq 1$: \begin{align*} \color{blue}{a_{n+1}}&=a^{[\emptyset]}_{n+1}+a^{[1]}_{n+1}+a^{[2]}_{n+1}+a^{[3]}_{n+1}\tag{$ \to (1)$}\\ &=4a^{[\emptyset]}_{n}+3a^{[1]}_{n}+3a^{[2]}_{n}+3a^{[3]}_{n}\tag{$\to (2),(3),(4),(5)$}\\ &=3a_n+a^{[\emptyset]}_{n}\tag{$ \to (1)$}\\ &=3a_n+\left(a^{[\emptyset]}_{n-1}+a^{[1]}_{n-1}+a^{[2]}_{n-1}+a^{[3]}_{n-1}\right)\tag{$ \to (2)$}\\ &\,\,\color{blue}{=3a_n+a_{n-1}}\tag{$\to (1)$} \end{align*} We derive the wanted recurrence relation for $a_n$ as \begin{align*} \color{blue}{a_{n}}&\color{blue}{=3a_{n-1}+a_{n-2}\qquad\qquad n\geq 2}\\ \color{blue}{a_0}&\color{blue}{=1}\\ \color{blue}{a_1}&\color{blue}{=4}\\ \end{align*} where we set $a_0=1$ for the empty sequence and $a_1=4$ according to the the number $|\mathcal{V}|=4$ of valid sequences of length $1$.

The first few values of the wanted recurrence relation are \begin{align*} \color{blue}{(a_n)_{n\geq 0}=\{1, 4, 13, 43, 142, 469, 1\ 549, 5\ 116, 16\ 897,\ldots\}} \end{align*} in accordance with A003688 from OEIS.

Note: This answer is given using a verbose and lengthy presentation. We could considerably reduce the length of the text by formulating the relationships using $a^{[j]}_{n}, j=1,2,3$.