Number of permutations of the sequence How can I find the number of permutations without repetitions of the sequence of all natural numbers from $1$ to $n$ such that every permutation starts with $1$ and ends with $n$ and the difference between any consecutive terms of permutation is no greater than $3$, i.e. $\lvert a_{i+1} - a_{i}\rvert\in\{1,2,3\}$?
Thanks!
 A: This was fairly tough and my solution is complicated.
The problem is equivalent to finding the number of ways to jump from square $0$ to square $n$ on a row of squares, without jumping further than three spaces at a time, and without missing any squares in between.
$$\begin{array}{c|cccc}
\blacksquare&\square&\square&\square&\ldots&\square\\
0&1&2&3&&n\end{array}$$
If you experiment a little with the problem, you will find that if you are not allowed to move more than two spaces at a time, then your progress from left to right is highly predictable. However, when you can move three spaces at a time, it is possible to make a sequence of long jumps to the right, double back once, and then return, having filled in all the squares you missed. The fact that the ways to do so are limited makes the problem tractable.
First, we start with an empty row, and shade the first square. We can then draw a vertical line after the first square, to remind us that all the squares to the left of the line have been filled. Let $f(n)$ be the number of ways to get to square n, obeying the rules.
Now, there are three possibilities: jump one square, jump two squares, or jump three squares.
In the first case:
$$\begin{array}{|ccccc}\blacksquare&\square&\square&\square&\ldots\end{array}$$
we could draw a new vertical line after the square just shaded, and we'd be in the exact same situation again, but with one square fewer. So from this point on, there are $f(n-1)$ ways to get to square $n$.
In the second case, we have the following situation:
$$\begin{array}{|ccccc}\square&\blacksquare&\square&\square&\ldots\end{array}$$
Let $g(n)$ be the number of ways to get to the last square from this configuration.
In the third case, we have:
$$\begin{array}{|cccccc}\square&\square&\blacksquare&\square&\square&\ldots\end{array}$$
Let $h(n)$ be the number of ways to get to the last square from this configuration.
The easy part is to see that $f(n)=f(n-1)+g(n-1)+h(n-1)$. After that it gets tricky.
In the second case, call the shaded square "1"; then the next moves can be 1-0-2 or 1-0-3 or 1-2-0-3 or 1-3-0-2-4 or 1-3-0-2-5, or 1-4... (long leaps to the right)
In the third case, call the shaded square "2"; then the next moves can be 2-0-1-3 or 2-0-1-4 or 2-1-0-3 (but only if all squares to the left of the line are filled) or 2-0-3-1-4 or 2-3-0-1-4 or 2-4-1-0-3-5 or 2-4-1-0-3-6, or 2-5... (long leaps to the right)
How can we deal with multiple leaps to the right? Actually, it's quite simple: let $\hat{h}(n)$ be the number of ways to get to square $n$ in the third case, if squares remain to be filled on the left of the vertical line. It turns out that the order in which those earlier squares get filled is entirely dependent on what happens to the right of the line.
Putting it all together:
$\begin{array}{rcl}f(n)&=&f(n-1)+g(n-1)+h(n-1)\\
g(n)&=&f(n-2)+f(n-3)+f(n-4)+g(n-2)+g(n-4)+\hat{h}(n-2)\\
h(n)&=&2f(n-3)+2f(n-4)+f(n-5)+g(n-3)+g(n-5)+\hat{h}(n-3)\\
\hat{h}(n)&=&h(n)-f(n-4)
\end{array}$
$$\begin{array}{c|ccccccccc}
n&0&1&2&3&4&5&6&7&\ldots\\
\hline f&1&1&1&2&6&14&28&56&\ldots\\
g&0&0&1&2&4&8&17&37&\ldots\\
h&0&0&0&2&4&6&11&25&\ldots\\
\hat{h}&0&0&0&2&3&5&10&23&\ldots
\end{array}$$
It is easy to continue this table using a computer. For example I found that, for one hundred squares, the answer is $f(99)=46103635399805799327514181735963$. I will add this sequence to the OEIS if you like.
Edit: I've found a simpler way to express the recurrence:
$$f(n)=1\cdot f(n-1)+0\cdot f(n-2)+1\cdot f(n-3)+3\cdot f(n-4)+...$$
The coefficients start $1, 0, 1, 3, 4, 5, 7, 10,$ and from that point each new coefficient is the sum of the last and the third-last, so $5+10=15,$ then $7+15=22,$ etc.
