counting sequences of elements of the set {1,2,3,4} with given property

Question

I found this problem in some internet olympiad-prep materials (don't remember the source of this file):

Find the number of $n$-element sequences $(a_1,a_2,\dots,a_n)$ such that $a_1=1$, $a_n=4$ and $a_i\in\{1,2,3,4\}$ and $|a_{i+1}-a_i|=1$ for all $i=1,\dots,n-1$.

Let $X_n$ be the number we want. Obvious values: $X_1=0$, $X_2=0$, $X_3=0$, generally $X_{2k-1}=0$ since we need to go from 1 to 4 and every step is $\pm 1$, so it changes the parity of our term. For the even $n$, I computed $X_4=1$ (as $(1,2,3,4)$ is the only one), $X_6=3$ (as $(1,2,1,2,3,4)$, $(1,2,3,2,3,4)$, $(1,2,3,4,3,4)$ are the only ones) and if I'm not mistaken $X_8=8$, $X_{10}=18$, $X_{12}=50$. Probably there is a recurrence relation between $X_{2k+2}$ and $X_{2k}$ or also previous terms, but I couldn't find it.

Answer 1

Disclaimer

This answer skips some details, but hopefully it's sufficient to guide you and let you research the details yourself.

The Answer

$$ x_{4+2m}= \left(\frac{5-3\sqrt{5}}{10}\right) \left(\frac{3-\sqrt{5}}{2}\right)^{m} + \left(\frac{5+3\sqrt{5}}{10}\right) \left(\frac{3+\sqrt{5}}{2}\right)^{m} $$

The Process

Define $y_{n}$ similar to $x_{n}$, except we have $a_{n}=2$. We have:

• $x_{4}=1$, the only sequence is $\left(1,2,3,4\right)$
• $y_{4}=2$, the sequences are $\left(1,2,3,2\right)$ and $\left(1,2,1,2\right)$

For a sequence to end with

• $4$, the sequence must end with $\left(...,4,3,4\right)$ or $\left(...,2,3,4\right)$
• $2$, the sequence must end with $\left(...,4,3,2\right)$, $\left(...,2,1,2\right)$, or $\left(...,2,3,2\right)$

Therefore, we obtain a recursion relation:

$$ \begin{pmatrix} x_{4+2m} \\ y_{4+2m} \end{pmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix} \begin{pmatrix} x_{4+2m-2} \\ y_{4+2m-2} \end{pmatrix} $$

or

$$ \begin{aligned} \begin{pmatrix} x_{4+2m} \\ y_{4+2m} \end{pmatrix} &= \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}^{m} \begin{pmatrix} x_{4} \\ y_{4} \end{pmatrix}\\\\ &= \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}^{m} \begin{pmatrix} 1 \\ 2 \end{pmatrix} \end{aligned} $$

Using the eigenvectors and eigenvalues of the square matrix, we obtain the explicit form of $x_{4+2m}$ above (and $y_{4+2m}$ but we don't need it).

Answer 2

Here's a recurrence I got.

Let $f_n$ be the number of ways to have such a sequence of length $n$ with $a_n = 2$.

Case 1: $a_{n-1}=1$

$a_{n-2}$ must be 2, this accounts for $f_{n-2}$ ways.

Case 2: $a_{n-1}=3, a_{n-2}=4$

This accounts for $X_{n-2}$ ways.

Case 3: $a_{n-1}=3, a_{n-2}=2$

This accounts for $f_{n-2}$ ways.

Thus, we get:

$f_n = 2f_{n-2}+X_{n-2}$ for $f_2=1$ and $n\ge4$.

Now we find the value of $X_n$ in terms of $f$.

When counting the number of ways in $X_n$, note that $a_{n-1}$ must equal 3.

Case 1: $a_{n-2}=2$

This accounts for $f_{n-2}$ ways.

Case 2: $a_{n-2}=4$

This can be done in $X_{n-2}$ ways.

Thus,

$X_n=X_{n-2}+f_{n-2}$

Let us expand this using the recursion for $f_n$.

$X_n=X_{n-2}+f_{n-2}=X_{n-2}+X_{n-4}+2f_{n-4}=X_{n-2}+X_{n-4}+2X_{n-6}+4f_{n-6}=\ldots=X_{n-2}+X_{n-4}+2X_{n-6}+4X_{n-8}+\ldots+2^{n/2 - 3}X_{n-n+2}+2^{n/2-2}f_2$

Note that $f_2$ is equal to $1$.

Using this recurrence relation, the first few terms are: $X_0=0$

$X_2=0$

$X_4=1$

$X_6=3$

$X_8=8$

$X_{10}=21$

$X_{12}=55$

Notice that $X_{2n}=F_{2n-2}$ where $F_k$ represents the $n$th Fibonnacci number. This can be proven by induction as this property is seen for $n=1, 2$. Also, for the inductive step, note that:

$X_n=X_{n-2}+f_{n-2}=X_{n-2}+2X_{n-2}-X_{n-4}=3X_{n-2}-X_{n-4}$

Fibonacci numbers also follow the recursion: $F_n=3F_{n-2}-F_{n-4}$