13
$\begingroup$

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!

$\endgroup$
9
  • 2
    $\begingroup$ This is A174700 in Sloane's. It doesn't look like there's any nice formula or generating function. $\endgroup$ – Jair Taylor Mar 4 '15 at 7:51
  • $\begingroup$ @JairTaylor: Nice reference - however the OP imposed another condition, namely that the sequence starts with a $1$ which affects the figures in a non-trivial way ... $\endgroup$ – String Mar 4 '15 at 7:55
  • 1
    $\begingroup$ The list of figures given the additional condition that the sequence should start with a $1$ begins like this: 1, 1, 2, 6, 18, 42, 90, 197, 442, 984, 2152, 4660, 10064, 21700, 46656, 99999, ... $\endgroup$ – String Mar 4 '15 at 8:36
  • 1
    $\begingroup$ The number of such permutations is sequence 1,1,1,2,6,14,28,56,118,254,541 and there is no record in OEIS for it. Even Wolfram's Mathematica is not able to find the recurrence with FindLinearRecurrence... $\endgroup$ – user144765 Mar 4 '15 at 9:28
  • 1
    $\begingroup$ Yes, given the last condition of ending with $n$ the first 20 figures read: 1, 1, 1, 2, 6, 14, 28, 56, 118, 254, 541, 1140, 2401, 5074, 10738, 22711, 48001, 101447. Thank you, @coffeemath. I wonder if a closed form would be possible, but perhaps the assumptions are too involved for that ...? $\endgroup$ – String Mar 4 '15 at 12:18
11
+100
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Oh very nice! I tried doing this at first but got stuck on the $\hat{h}(n)$ case. $\endgroup$ – Andrew Szymczak Mar 7 '15 at 3:44
  • $\begingroup$ Do you have a combinatorial explanation for the simpler expression or did you just expand the $g,h,\hat{h}$ recurrences? $\endgroup$ – Andrew Szymczak Mar 7 '15 at 7:01
  • 3
    $\begingroup$ Your sequence satisfies the recurrence relation $f(n) = 2f(n-1) - f(n-2) + 2f(n-3) + f(n-4) + f(n-5) - f(n-7) - f(n-8)$ with initial values $f(0),\ldots,f(7) = 1,1,1,2,6,14,28,56$. Therefore $f(n) = \Theta(\alpha^n)$, where $\alpha \approx 2.11393$ is the maximal real root of $x^8-2x^7+x^6-2x^5-x^4-x^3+x+1$. $\endgroup$ – Yuval Filmus Mar 7 '15 at 7:02
  • $\begingroup$ Nice @YuvalFilmus I found a slightly different expression for the characteristic polynomial, leading to the recurrence $$ f_n = f_{n-1} + f_{n-2} + f_{n-3} + 3f_{n-4} + 2f_{n-5} + f_{n-6} - f_{n-7} - 2f_{n-8} - f_{n-9}$$ $\endgroup$ – Andrew Szymczak Mar 7 '15 at 7:13
  • $\begingroup$ My recurrence is minimal. The sequence doesn't satisfy any shorter linear relation. $\endgroup$ – Yuval Filmus Mar 7 '15 at 7:14
8
$\begingroup$

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$ enter image description here

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.

$\endgroup$
14
  • $\begingroup$ You can find the characteristic equation, which happens to have degree $8$, in my comment to Andrew's answer. $\endgroup$ – Yuval Filmus Mar 7 '15 at 7:05
  • $\begingroup$ @YuvalFilmus how did you calculate the characteristic equation? I used Matlab to get a ninth order equation -- how did you reduce it to eighth order? $\endgroup$ – Andrew Szymczak Mar 7 '15 at 7:23
  • 2
    $\begingroup$ I calculated many terms of the sequence, then computed a matrix with $n$ rows of length $m$, each containing $m$ consecutive elements of the sequence. I then computed the kernel. If it's not empty for "large" $n$ and the appropriate $m$, there is a linear relation. If it is empty (i.e. contains only the zero vector), them $m$ is too small. $\endgroup$ – Yuval Filmus Mar 7 '15 at 7:26
  • $\begingroup$ @YuvalFilmus: Good team-work! +1 for all of You! :-) $\endgroup$ – Markus Scheuer Mar 7 '15 at 9:16
  • $\begingroup$ Can you tell which tool to use for fast matrix exponentiation? Or provide code snippet? Now I have linear recurrence of 120th order and it is needed to compute 10^14th term. I'm stuck with Python implementation... $\endgroup$ – user144765 Mar 13 '15 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.