9
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ This seems easy enough to brute force with code. By my count, I'm getting $X_{10}=21$ and $X_{12}=55$, $X_{14}=144$. Looking at oeis it would appear to be oeis.org/A001906 though admittedly I don't yet see the connection $\endgroup$
    – JMoravitz
    Nov 30, 2023 at 3:46
  • 1
    $\begingroup$ Dirty code in javascript: counter = function(k){count = 0; for(x=2**k; x<2**(k+1); x++){xstr = x.toString(2); outputstr=''; flag = true; lead=0; for(y=1; y<xstr.length; y++){ lead += (+xstr[y] || -1); if (lead<=0 || lead>4){ flag=false; break; } outputstr += '' + lead;} if (lead==4){ console.log(outputstr); count+=1;}} return count;} Opening dev console with F12 in most browsers and pasting that in, you can run count(10) to see the 21 different valid sequences in question. $\endgroup$
    – JMoravitz
    Nov 30, 2023 at 3:52
  • $\begingroup$ Adjusting the code to accept an optional parameter to replace the original upper bound of 4, using an upper bound of 6 instead leads to oeis.org/A005021 and from there I expect the citations if you have access to them should hopefully take you the rest of the way to understanding the problem. Perhaps someone else can explain the special case of 4 and its relation to Fibonacci. Else, I'll sleep on it and might revisit it again tomorrow. $\endgroup$
    – JMoravitz
    Nov 30, 2023 at 4:04
  • $\begingroup$ Something to think about: image $\endgroup$ Nov 30, 2023 at 5:09
  • $\begingroup$ You may find it easier to define four sequences rather than one: $X_{1,n},X_{2,n},X_{3,n},X_{4,n}$, where $X_{i,n}$ is the number of sequences that start at $1$ and end at $i$ after $n$ steps. Then the four recurrences are quite easy to write down in terms of each other. $\endgroup$ Nov 30, 2023 at 20:57

2 Answers 2

7
$\begingroup$

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).

$\endgroup$
1
  • 1
    $\begingroup$ Note: One may also see from this the recurrence relation $x_{4+2m} = 3x_{4+2m-2} - x_{4+2m-4}$ $\endgroup$
    – Cecilia
    Nov 30, 2023 at 19:39
2
$\begingroup$

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}$

$\endgroup$
5
  • $\begingroup$ I guess it's not a coincidence that $X_{2n}=F_{2n-2}$ (Fibonacci number) for $n\gt0$? $\endgroup$
    – bof
    Nov 30, 2023 at 6:45
  • $\begingroup$ I notice that now but can't find a proof for it. Do you have a proof? $\endgroup$ Nov 30, 2023 at 8:28
  • 2
    $\begingroup$ I didn't have a proof when I posted my previous comment but I think I have one now. According to your equations, $$X_n=X_{n-2}+f_{n-2}=X_{n-2}+(2X_{n-2}-X_{n-4})=3X_{n-2}-X_{n-4}.$$ Since the Fibonacci numbers also satisfy the recurrence $$F_n=3F_{n-2}-F_{n-4},$$ and since the identity $X_{2n}=F_{2n-2}$ holds for $n=1$ and $n=2$, it follows by induction that it holds for all $n$. Right? $\endgroup$
    – bof
    Nov 30, 2023 at 9:44
  • $\begingroup$ This is great! Why don't you post this as an answer? Because the formula for Fibonacci numbers gives a closed form answer to the question. $\endgroup$ Nov 30, 2023 at 10:20
  • $\begingroup$ It's not a standalone answer since it builds on your answer. Why don't you edit your answer to include this refinement? $\endgroup$
    – bof
    Nov 30, 2023 at 12:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .