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!

Solution 1:

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.

Solution 2:

See the second part for a discussion of Andrew's solution

This problem is equivalent to counting the number of Hamiltonian paths in the generalization of the following graph (n=8)

$\qquad \qquad \qquad \qquad \qquad \quad$

Of course, this doesn't necessarily mean that the problem is NP-hard, since these graphs are "nice" (symmetric, degree<7, etc). Using the typical dynamic programming algorithm which counts by ({nodes visited}, current node) I managed to count the permutations for $n\le30$.

$$ \begin{array} ( & \\ 1 & 1 & 1 & 2 & 6 \\ 14 & 28 & 56 & 118 & 254 \\ 541 & 1140 & 2401 & 5074 & 10738 \\ 22711 & 48001 & 101447 & 214446 & 453355 \\ 958395 & 2025963 & 4282685 & 9053286 & 19138115 \\ 40456779 & 85522862 & 180789396 & 382176531 & 807895636 \\ & \\ & \\ \end{array} $$

$$ \qquad $$

Andrew Woods posted a very nice solution here. I just want to add a few things. First note his offset for the sequence (my $a_n$ equals his $f_{n-1}$). Because we have a linear recurrence, we can use the matrix-exponentiation method to calculate the value $a_n$ for very large values of $n$. For example, $$ \begin{array} ( a_{100} &= 46103635399805799327514181735963 \qquad \checkmark \\ a_{10^{10000}} &= 75922134066658345530 \; \left(\,\text{mod } 10^{20}\,\right) \end{array} $$

The recurrence matrix $M$ and initial vector $b$ are

$$ \tiny M = \left( \begin{array} ( . & 1 & . & . & . & . & . & . & . & . & . & . & . \\ . & . & 1 & . & . & . & . & . & . & . & . & . & . \\ . & . & . & 1 & . & . & . & . & . & . & . & . & . \\ . & . & . & . & 1 & . & . & . & . & . & . & . & . \\ . & . & . & . & 1 & . & . & . & . & 1 & 1 & . & . \\ . & . & . & . & . & . & 1 & . & . & . & . & . & . \\ . & . & . & . & . & . & . & 1 & . & . & . & . & . \\ . & . & . & . & . & . & . & . & 1 & . & . & . & . \\ . & . & . & . & . & . & . & . & . & 1 & . & . & . \\ . & 1 & 1 & 1 & . & . & 1 & . & 1 & . & . & . & 1 \\ 1 & 2 & 2 & . & . & 1 & . & 1 & . & . & . & 1 & . \\ . & . & . & . & . & . & . & . & . & . & . & . & 1 \\ -1 & . & . & . & . & . & . & . & . & . & 1 & . & . \\ \end{array} \right) \qquad b = \left( \begin{array} ( f_0 \\ f_1 \\ f_2 \\ f_3 \\ f_4 \\ g_0 \\ g_1 \\ g_2 \\ g_3 \\ g_4 \\ h_4 \\ \hat{h}_2 \\ \hat{h}_3 \\ \end{array} \right) = \left( \begin{array} ( 1\\1\\1\\2\\6\\0\\0\\1\\2\\4\\4\\0\\2\\ \end{array} \right) $$

where the omitted values are all zeros. Then $a_n$ is simply the first coordinate of $M^{n-1} b$. The next step is to find the characteristic equation of $M$.

You can find the characteristic equation of $M$ using Matlab's $\texttt{charpoly}$ command, which yields $x^{13} - x^{12} - x^{11} - x^{10} - 3x^9 - 2x^8 - x^7 + x^6 + 2x^5 + x^4 $, giving us the recurrence $$a_n = a_{n-1} + a_{n-2} + a_{n-3} + 3a_{n-4} + 2a_{n-5} + a_{n-6} -a_{n-7} - 2a_{n-8} -a_{n-9} $$

Yuval Filmus calculated the characteristic equation using a different method, yielding the minimal linear recurrence

$$ a_n = 2a_{n-1} - a_{n-2} + 2a_{n-3} + a_{n-4} + a_{n-5} - a_{n-7} - a_{n-8} $$

Note that if you subtract the second recurrence from the first, you get the second recurrence shifted by one (the term corresponding to the root (-1) vanishes). To be complete, another interesting recurrence that Andrew found is

$$ \begin{array} ( a_n &= a_{n-1} + a_{n-3} + 3a_{n-4} + 4a_{n-5} + 5a_{n-6} + 7a_{n-7} + 10a_{n-8} + ... \\ &:= \sum_{i\ge1}{c_i a_{n-i}} \end{array} $$

where the coefficient $c_i = c_{i-1} + c_{i-3}$ for $i>8$. I presume that he found this recurrence by expanding the recurrences $g,h,\hat{h}$ from his post (that's how I found it). Finally, as Yuval noted, we get a growth rate $a_n = \Theta(\gamma^n)$ where $\gamma \approx 2.11393$ is the magnitude of the largest root of the characteristic equation.