sequences above 0,1,2 start&end with 0 with no 2 same successive digits

Question

find the number of sequences of length n above {0,1,2} that start and end with 0 and without 2 successive digits that are equal (00,11,22). Find and solve a recursice equation.

I would be thankful for a clue or an approach to this.

Answer 1

We define a recurrence relation as follows. Let

• $a_k$ denote the number of valid strings with $k$-th symbol $0$.

• $b_k$ denote the number of valid strings with $k$-th symbol $1$.

• $c_k$ denote the number of valid strings with $k$-th symbol $2$.

Since valid strings start with $0$ we have \begin{align*} a_1=1\qquad b_1=0\qquad c_1=0\tag{1} \end{align*}

Valid strings do not have equal consecutive characters. The recurrence relation for $2\leq k\leq n-1$ is \begin{align*} a_k&=b_{k-1}+c_{k-1}\\ b_k&=a_{k-1}+c_{k-1}\tag{2}\\ c_k&=a_{k-1}+b_{k-1} \end{align*} and since the $n$-th character of a valid string is $0$, we have for $n\geq 2$: \begin{align*} a_n=b_{n-1}+c_{n-1}\tag{3} \end{align*}

We are looking for $a_n, n\geq 0$.

Due to the symmetry of $b_n$ and $c_n$ in the recurrence relations (1) - (3) we observe $b_n=c_n, n\geq 1$ and we obtain a simplified recurrence relation

\begin{align*} a_1&=1, b_1=0\\ a_k&=2b_{k-1}\qquad\qquad 2\leq k\leq n-1\tag{4}\\ b_k&=a_{k-1}+b_{k-1}\\ a_n&=2b_{n-1}\tag{5} \end{align*}

We obtain from (4) a recurrence relation for $b_k, k\geq 1$. \begin{align*} b_1&=0, b_2=1\\ b_k&=b_{k-1}+2b_{k-2}\qquad\qquad k\geq 3\tag{6} \end{align*}

Setting $B(x)=\sum_{k=0}^\infty b_kx^k$ we obtain from (6) \begin{align*} \sum_{k=3}^\infty b_kx^k&=\sum_{k=3}^\infty b_{k-1}x^k+2\sum_{k=3}b_{k-2}x^k\\ &=x\sum_{k=2}^\infty b_{k}x^k+2x^2\sum_{k=1}b_{k}x^k\\ B(x)-x^3&=xB(x)+2x^2B(x)\\ \color{blue}{B(x)}&\color{blue}{=\frac{x^3}{1-x-2x^2}} \end{align*}

Since $a_n=2b_{n-1}$ according to (5), we finally obtain for $n\geq 2$ \begin{align*} a_n&=2[x^{n-1}]B(x)\\ &=2[x^n]xB(x)\\ &=[x^n]\frac{2x^3}{1-x-2x^2}\\ &=[x^n]\left(2 x^3 + 2 x^4 + 6 x^5 + \color{blue}{10} x^6 + 22 x^7 + 42 x^8 + \cdots\right) \end{align*}

The last line was calculated with some help of Wolfram Alpha.

The coefficient $\color{blue}{10}$ of $x^6$ for example tells us we have $10$ valid strings \begin{align*} &010120,010210,012010,012020,012120,\\ &020120,020210,021010,021020,021210 \end{align*}

Answer 2

It's the number of closed walks on the graph $K_3$. So if we define $$ A= \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix} $$ then it's the number in cell $(1,1)$ of $A^n$.

Computing this gives $$ 0, 2, 2, 6, 10, 22, 42, 86, 170, 342, 682, \ldots $$ when $n \geq 1$, which is OEIS's A078008.

There's a linear recurrence given there $$ a(n) = 3a(n-2) + 2a(n-3) $$ which follows directly from the identity $$ A^4 = 3A^2+2A. $$ And if we use the usual methods for solving linear recurrences, we'd get the closed form solution at OEIS: $$ a(n) = \frac{1}{3}(2^n + 2(-1)^n). $$