Count the number of 10 digit numbers with given condition

Question

PROBLEM: Count the number of 10 digit numbers with digits from $\{1, 2, 3, 4\}$ and no two adjacent digits differing by $1$.

---

I am able to provide a solution using recursion but it is a very tedious(non elegant) one using two recurrence relations.

I let $a_n, b_n, c_n, d_n$ be the number of $n$ digit numbers satisfying the conditions of the problem and ending in $1, 2, 3, 4$ respectively. Then its easy to see that I got the following recursions:

$b_{n+1}=b_n+a_n$; $a_{n+1}=2a_n+b_n$; $a_n=d_n$ and $b_n=c_n$ The first two give $b_{n+2}-3b_{n+1}+b_{n}=0$ with $b_1=1, b_2=2$. Now I can solve the recurrence and find $2(a_n+b_n)$ which is the required answer.

But I am looking for a neater or an alernative way of doing this problem (maybe with just one recurrence). So, please help.

Answer 1

Consider the following adjacency matrix: $$ M = \begin{pmatrix}0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{pmatrix}$$ associated with $\fbox{3}\leftrightarrow\fbox{1}\leftrightarrow\fbox{4}\leftrightarrow\fbox{2}$. The number of the wanted strings is given by: $$ N = (1,1,1,1)\, M^{10} (1,1,1,1)^T $$ but: $$ M^{10} = \begin{pmatrix} 89 & 55 & 0 & 0 \\ 55 & 34 & 0 & 0 \\ 0 & 0 & 34 & 55 \\ 0 & 0 & 55 & 89 \end{pmatrix} $$ since $M$ is a block matrix and the entries of $M^n$ are Fibonacci numbers.

It follows that $N=\color{red}{466}=2\cdot F_{13}$.

Answer 2

In general, if you have $k$ really different cases, you need $k$ recurrences, corresponding to $k$ state transitions. In this particular problem the two cases are whether the last digit is at the end of the range or not, so you need at least two recurrences. This also shows that two recurrences is enough for the problem where the digits can be from $0$ to $9$.