Number of sequences length n in which neighboring elements differ by 1

Question

Suppose we're given a set $S=\{1,2,3,4,5\}$. From elements in $S$, we form an array/sequence of length $n$, such that difference between neighboring elements is strictly $1$. For example, one valid sequence of length $n = 5$ is $32345$. What is the generating function for the number of such sequences?

My approach is to let $f(n)$ be a number of such sequences starting with 1 or 5 (only one neighboring number). Then, $f(n) = 2 * n-1$. Similiarly, let $g(n)$ be a number of sequences staring with $2,3,4$. Unfortunately, I can't find a proper formula for $g(n)$, although I'm quite convinced it's in the form of $a\times g(n-1) + b\times f(n-1)$.

Answer 1

Here is an alternative approach which you may find interesting.

What you want to count is the same as the number of walks of length $k$ in this graph:

This is given by the trace of the $k$'th power of its adjacency matrix $\begin{pmatrix} 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}$

In order to get a formula for these entries we can diagonalize the matrix.

The spectrum of the path $P_n$ is $2\cos(\frac{j\pi}{n+1})$ where $1\leq j \leq n$.

An orthogonal basis for the respective eigenvectors is $U_{i,j} = \frac{\sqrt{2} \sin(ij\pi/(n+1))}{\sqrt{n+1}}$

Hence we have $A=UDU^{-1}$ and $A^k = UD^kU^{-1}$. This gives us a a linear formula for the number of sequences of length $k$, in which the variables are the elements of the spectrum raised to the $k$.

Answer 2

Let $a_n$ be the number of sequences of length $n$ starting with $2$ (by symmetry, this is the same as the number starting with $4$).

Now there are three options for the next two numbers in the sequence: it must start $234$, $232$ or $212$. In each case, there are $a_{n-2}$ choices for the rest of the sequence: after removing the first two places we have a sequence of $n-2$ terms starting with $2$ or, in one case, $4$. So $a_n=3a_{n-2}$, which together with $a_1=1$ and $a_2=2$ gives $a_n=3^{\lfloor n/2\rfloor}$ if $n$ is odd and $a_n=3^{\lfloor n/2\rfloor-1}\cdot2$ if $n$ is even.

Now it should be easy to calculate the number of sequences of length $n$ starting with $1$, $3$ or $5$ in terms of $a_{n-1}$.

Answer 3

We can enumerate "by hand" the numbers of sequences of increasing length and ending in every number $$(1,1,1,1,1)\to(1,2,2,2,1)\to(2,3,4,3,2)\to(3,6,6,6,3)=3\times(1,2,2,2,1)$$ (it suffices to copy $n_1$ from $n_2$ and $n_5$ from $n_4$, and get the other counts by adding two antecedents).

You notice that the counts for $n=4$ are the triples of those for $n=2$, so that the pattern repeats on every other length, to an exponential factor, and we will have in total $8\cdot3^n$ and $14\cdot3^n$ distinct sequences of length $2n$ and $2n+1$ (except for the first).

The generating function follows easily as the sum of two geometric sequences.

$$5+(8+14x)\frac{3x^2}{1-3x^2}=\frac{5+9x^2+42x^3}{1-3x^2}.$$