Permutations of 15

Suppose there are $n_k$ ways to create a list of numbers $1$ to $k$ as specified in the question - effectively that the gap between each of the terms is $2$ or lower. We will find a way to relate $n_k$ to $n_{k-1}$ (and other previous terms), then find $n_{15}$ .

Consider how to start the sequence; so long as $k\geq5$ , it could begin in one of three ways - $(1,2, \ldots)$ , $(1, 3, 2, 4, \ldots)$ or $(1, 3, 5, \ldots)$ . Note that $(1, 3, 4, \ldots)$ is impossible because then there is no way to reach $2$ except from $4$ , so $2$ must come next, but there is no way to proceed from there to $5$ or higher.

If it begins $1, 2, \ldots$ , then another sequence is needed from $2$ to $k$ . This is just like taking a sequence from $1$ to $k-1$ (of which there are $n_{k-1}$ possibilities) and adding $1$ to each term, so there are $n_{k-1}$ possibilities starting with $1,2,\ldots$ .

If it begins $1, 3, 2, 4, \ldots$ , then a sequence from $4$ to $k$ is needed, which is like a sequence from $1$ to $k-3$ . There are therefore $n_{k-3}$ possibilities starting with $1, 3, 2, 4, \ldots$ .

If it begins $1, 3, 5, \ldots$ , then only one sequence is possible - either $(1, 3, 5, 7, \ldots, k, k-1, k-3, \ldots, 4, 2)$ or $(1, 3, 5, 7, \ldots, k-1, k, k-2, \ldots, 4, 2)$ , depending on whether $k$ is even or odd. To see this, consider where $2$ must go - the only available number it can be adjacent to is $4$ , so it must be at the end of the list. In order to go all the way up to $k$ and back to $2$ , all the odd numbers must be chosen in order; if two adjacent numbers are chosen, then that leaves a 'gap' 2 wide that cannot be crossed on the way back. The precise configuration at the end depends on whether $k$ is even or odd, but doesn't matter for counting. What is important is that there is only $1$ way to begin $1, 3, 5, \ldots$ .

Adding these possibilities together, we get that $n_k = n_{k-1} + n_{k-3} + 1$ . By inspection, we see there is only one way to have a list going up to $1$ or $2$ , while there are 2 ways ( $(1, 2, 3), (1, 3, 2))$ to go up to $3$ and 4 ways ( $(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2))$ to go up to $4$ ; so $n_1 = n_2 = 1, n_3 = 2, n_4 = 4$ . The recursion can then be applied up to $n_{15}$ -

$n_5 = 4 + 1 + 1 = 6$

$n_6 = 6 + 2 + 1 = 9$

$n_7 = 9 + 4 + 1 = 14$

$n_8 = 14 + 6 + 1 = 21$

$n_9 = 21 + 9 + 1 = 31$

$n_{10} = 31 + 14 + 1 = 46$

$n_{11} = 46 + 21 + 1 = 68$

$n_{12} = 68 + 21 + 1 = 100$

$n_{13} = 100 + 46 + 1 = 147$

$n_{14} = 147 + 68 + 1 = 216$

$n_{15} = 216 + 100 + 1 = \underline{317}$

First we explain the restriction presented in the problem.

Since $| \sigma(n) -\sigma(n-1)| \leq 2$ , then whenever $\sigma(n) = x$ then $\sigma(n-1)$ can only have a value of $x-2, x-1, x+1$ or $x+2$ .

Now for formality, I’ll define JUMP at $n^{th}$ term ass $| \sigma(n) -\sigma(n-1)| = 2$ . I’ll also define $i_k (n)=n$ , for $n=1,2, … , k$ , i.e., the identity mapping for $1, 2, .. , k$ .

First on the list is the Permutation without any jump. That is the $i_{15} (n)$ is $\left\{1, 2, 3, 4, … , 12, 13, 14, 15\right \}$

Since jumping cannot be performed in the 14th and 15th term of the permutation, the next permutation will be the one with the jump at 13th term. That is, $\left\{1, 2, 3, 4, … , 12, 13, 15, 14\right\}$

Thus we already have two permutations. Now we call the set of permutations $\left\{\left\{14,15\right\}, \left\{15, 14\right\}\right\}$ as $A_{13}$ .

Next, we JUMP on the $12^{th}$ term, that is, thus we produce another two permutations which are $\left\{1, 2, 3, 4, … , 10, 11, 12, 14, 13, 15\right\} \left\{1, 2, 3, 4, … , 10, 11, 12, 14, 15,13\right\}$

Thus we already have 4 permutations. Now we call the set of permutations $\left\{ \left\{13,14,15\right\}, \left\{13,15,14\right\}, \left\{14,13,15\right\}, \left\{14,15,13\right\} \right\}$ as $A_{12}$

Next, we JUMP on the $11^{th}$ term, that is, thus we produce another two permutations which are $\left\{1, 2, 3, 4, … , 10, 11, 13, 12, 14, 15\right\}$ $\left\{1, 2, 3, 4, … , 10, 11, 13, 15, 14, 12\right\}$

Thus we now have 6 different permutation. Now we call the set of permutations $\left\{ \left\{12,13,14,15 \right\}, \left\{12,13,15, 14\right\}, \left\{12,14, 13,15\right\}, \left\{12,14,15,13\right\},\left\{13,12,14,15\right\}, \left\{13,15,14,12 \right\} \right\}$ as $A_{11}$ .

In general, if we perform the jump in $r^{th}$ term, we get the set of permutation $A_r$ as the set of the last $(15-r)$ terms of the permutation mapping we have produced.

Now, noticed that if we perform a jump on $11^{th}$ term, that leaves 12 and goes directly to 13, we can't next to 14 because it will leave 12 as not a part of the permutation. That is, $\left\{ 1,2,3,4,5,6,7,8,9,10,11,13,14,15,12\right\}$ are excluded by the restriction $| \sigma(n) -\sigma(n-1)| \leq 2$ because $|\sigma(14)-\sigma(15)| = 15 - 12 = 3$ which is not less than or equal to $2$ . Thus if we perform the jump 10th term, it is either we go back by one then jump again, $\left\{1,2,3,4,…,10,12,11,13, *,*\right\}$ or continuously jump until we reach the maximum value and return again jumping $\left\{1,2,3,4,…,10,12,14,15,(then go back jumping) 13, 11\right\}$

Notice that $\left\{1,2,3,4,…,10,12,11,13,*,*\right\}$ can be continued by any element of $A_{13}$ , i.e, $\left\{1,2,3,4,…,10,12,11,13,14,15\right\}$ and $\left\{1,2,3,4,…,10,12,11,13,15,14\right\}$ .

And produce one which continuously jump and return $\left\{1,2,3,4,…10,12,14,15,13,11\right\}$ . Thus $A_{10}$ has a cardinality of $9$ .

Same thing as performing the jump at $9^{th}$ term, we have $\left\{1,2,3,4,…,9,8,10, ..\right\}$ which can be continued by each element of the set $A_12$ and one which continuously jump $\left\{1,2,3,4,…,9,11,13,15,14,12,10\right\}$ .

Thus, $|A_{10}|= |A_{11}| + |A_{13}| + 1$ and $|A_{9}| = |A_{10}|+| A_{12}| +1…$ As we continue the process, we can have the recurrence formula $|A_n|= |A_{n+1}|+|A_{n+3}|+1$ for $1 \leq n \leq10$ .

And to answer the problem, we only need to know the value of $A_1$ . $|A_{13}|=2$

$|A_{12}|=4$

$|A_{11}|=6$

$|A_{10}|=|A_{11}| + |A_{13}| + 1=6+2+1=9$

$|A_9|=|A_{10}|+|A_{12}|+1 =9+4+1=14$

$|A_8|=|A_9|+|A_{11}|+1=14+6+1=21$

$|A_7|=|A_8|+|A_{10}|+1=21+9+1=31$

$|A_6|=|A_7|+|A_9|+1=31+14+1=46$

$|A_5|=|A_6|+|A_8|+1=46+21+1=68$

$|A_4|=|A_5|+|A_7|+1=68+31+1=100$

$|A_3|=|A_4|+|A_6|+1=100+46+1=147$

$|A_2|=|A_3|+|A_5|+1=147+68+1=216$

$|A_1|=|A_2|+|A_4|+1=216+100+1=317$

Where I got $317$ .

Let's solve the generalized problem, using the set $\{1,2,...,n\}$ , and call $f_n$ it's solution. In the proposed problem, we are interested in $f_{15}$ .

$\sigma(1) = 1$ , so $\sigma(2)$ must be either $2$ or $3$ (since $|\sigma(2)-1|\leq 2$ ).

$\bullet$ If $\sigma(2) = 2$ , then we have a similar problem, with the set $\{2,3,...,n\}$ and $\sigma(2) = 2$ . It's easy to see that the solution to this sub problem is $f_{n-1}$ .

$\bullet$ If $\sigma(2) = 3$ , then $\sigma(3)$ may be $2$ . But $\sigma(3) = 2 \Rightarrow \sigma(4) = 4$ (since $|\sigma(4)-2|\leq 2$ , and $1,2$ and $3$ were already used). Using a similar argument, the solution to this sub problem is $f_{n-3}$ .

$\bullet$ If $\sigma(2)=3$ and $\sigma(3)\neq 2$ , there must be a $x$ such that $\sigma(x) = 2$ . It's neighbors must have distance at most 2, but there is only one such number left: $4$ . Therefore $x$ must have only one neighbor, and we conclude that $x = n$ . So we have $\sigma(1) = 1,\sigma(2) = 3, \sigma(n) = 2, \sigma(n-1) = 4$ .

We will now use induction to show that there is only one possible permutation satisfying these restrictions. Suppose that $\sigma(1)=1,\sigma(2)=3,...,\sigma(k+1)=2k+1$ and $\sigma(n)=2,...,\sigma(n-k+1)=2k$ . Then if $2k+2\leq n$ we must have $\sigma(n-k)=2k+2$ (since $|\sigma(n-k)-2k|\leq 2$ , and $\sigma(n-k)$ cannot be $2k-2,2k-1,2k$ or $2k+1$ ). Similarly if $2k+3\leq n$ we must have $\sigma(k+2)=2k+3$ . So we conclude that the only permutation satisfying $\sigma(1) = 1,\sigma(2) = 3, \sigma(n) = 2$ is $\{1,3,5,...,n,...6,4,2\}$ .

All the above is valid iff $n\geq 4$ . So for $n\geq 4$ we have $f_{n-1}$ permutations such that $\sigma(2)=2$ , $f_{n-3}$ permutations such that $\sigma(2)=3$ and $\sigma(3)=2$ and we have 1 permutation such that $\sigma(2)=3$ and $\sigma(3)\neq 2$ . These are obviously all possible permutations, so we arrive at the recursive equation $f_{n} = f_{n-1} + f_{n-3} + 1$ . Also it's easy to see that $f_1=1 , f_2=1$ and $f_3=2$ , therefore we have arrived at the solution:

$\bullet f_{n} = f_{n-1} + f_{n-3} + 1|f_1=1 , f_2=1$ and $f_3=2$ .

Now, we could arrive at a closed formula for $f_n$ , but that would involve finding the roots of a $4^{th}$ degree polynomial . Instead we can simply calculate $f_n$ one by one: $1,1,2,4,6,9,14,21,31,46,68,100,147,216,317_\blacksquare$

Denote the number of permutations of {1,2,...,n} that satisfy the conditions be p(n)

We know that a 1=1, so a 2 is either 2 or 3.

If a_2=2, then the remaining numbers form a permutation of 3, 4, ..., n.

If we subtract 1 from all the a_i's where 2 \le i \le n, then we get a permutation of {1,2,...,n-1} that satisfies the conditions.

Hence, if a_2=2, there are p(n-1) permutations.

If a 2=3, then a 3 could be 2, 4, or 5.

If a 3=2, then a 4 must be 4. This means that if we subtract 3 from all of the a_i's such that 4 \le i \le n, then we get a permutation of {1,2,...,n-3} that satisfies the conditions. Hence there are p(n-3) permutations.

If a 3=4, then we consider where would 2 go. 2 could only be beside 1, 3, or 4. This means that 2 must be a 4. However, the number at the right of 2 would differ from 2 by at most 3 (note that the least possible number at the right of 2 is 5). Hence, there is no such permutation.

If a 3=5, note that we have skipped 2. The only possible numbers that could be beside 2 are 1, 2, 3, or 4. Since 1 and 3 could not already be beside 2, 4 and 2 are adjacent and are at the last 2. Then note that 4 could only be beside 2, 3, 5, 6. Since 4 is at the 2nd to the last order in the permutation, the number that is at the 3rd to the last order is 6. 5 could only be beside 3, 4, 6, 7, so a 4=7. We could similarly fill up the remaining cells to get 1, 3, 5, 7, 9, 11, 13, 15, 14, 12, 10, 8, 6, 4, 2, or in a more general form, 1, 3, ..., n, n-1, n-3, ..., 2 if n is odd and 1, 3, ..., n-1, n, n-2, ..., 2 if n is even. Hence, there is 1 such permutation in this case.

In total, there are p(n-1)+p(n-3)+1 permutations.

If n=1, there is only 1 permutation: (1). If n=2, there are 2 permutations: (1,2) If n=3, there are 2 permutations: (1,2,3), (1,3,2) Thus p(1)=1, p(2)=1, p(3)=2

p(4)=2+1+1=4 p(5)=4+1+1=6 p(6)=6+2+1=9 p(7)=9+4+1=14 p(8)=14+6+1=21 p(9)=21+9+1=31 p(10)=31+14+1=46 p(11)=46+21+1=68 p(12)=67+31+1=100 p(13)=99+46+1=147 p(14)=146+67+1=216 p(15)=216+100+1=317

Hence, there are 317 such permutations that satisfy the conditions.

P.S. Please LaTeX this for me. By the way, why have you not responded to my emails?

Let the number of permutations $\sigma$ of the set $\{1,2,3,\dots,n\}$ that satisfy the condition is $a_n$
We can easily find that $a_1=1, a_2=1, a_3=2$
We will find the reccurence relation for $n>3$
We divide into 2 cases:
1. $\sigma(2)=2$
If $\sigma(2)=2$ , then the set becomes $\{1,2,...,n\}$
We can ignore the first term, which is $1$ , and count the number of permutations of $\{2,3,...,n\}$
The number of permutations of set $\{2,3...,n\}$ is equal with the number of permutations of $\{1,2,...,n-1\}$ So, the number of permutations of set $\{2,3,...,n\}$ is $a_{n-1}$
Therefore, there are $a_{n-1}$ permutations in this case.
2. $\sigma(2)=3$
We will divide this case into 3 subcases:
Subcase 1: $\sigma(3)=2$
If $\sigma(3)=2$ , then $\sigma(4)$ must be $4$
The set becomes $\{1,3,2,4,...\}$
Since the first 3 terms is fixed, we can ignore the first 3 term
Therefore, we only need to count the number of permutations of $\{4,5,...,n\}$ which is equal with the number of permutations of $\{1,2,...,n-3\}$
So, the number of permutations of $\{1,3,2,4,...\}$ is $a_{n-3}$
Subcase 2: $\sigma(3)=4$
If $\sigma(4)\neq2$ , then $2$ can't be placed in the set because 2 must be placed beside 1,3,or 4, while 1,3,and 4 have been used as the first 3 terms
If $\sigma(4)=2$ , then we can't put the other number in the set because $|\sigma(4)-\sigma(5)| = |2-x| > 2$ ( $x$ is more than $4$ )
So, the number of permutations of $\{1,3,4,...\}$ is 0
Subcase 3: $\sigma(3)=5$
We can easily find that the only permutation of this subcase is $\{1,3,5,7,...,n,...,6,4,2\}$
So, the number of permutation in this subcase is 1
From all cases, we get $a_n = a_{n-1} + a_{n-3} + 1$ with $a_1=1, a_2=1, a_3=2$
By substituting the value of $n$ from 4 to 15, we get $a_{15}=317$

To solve this problem we will need to generalize it to other lengths of permutation besides 15. For convenience we'll call any permutation $\sigma$ "nice" if $|\sigma(n) - \sigma(n-1)| \le 2$ for all choices of $n$ that make sense.

Let $a_k$ be the number of nice permutations of $\{1,\ldots,k\}$ that start with 1, and let $b_k$ be the number of nice permutations of $\{1,\ldots,k\}$ that start with 2. Of course we are interested in $a_{15}$ , but $b_k$ will turn out to be useful in our calculations.

For small values of $k$ it is very easy to check that $a_1 = a_2 = 1, a_3 = 2$ . Let's look for a recurrence that will allows us to compute larger values of $a_k$ based on smaller ones.

Consider a permutation $\sigma$ which satisfies the conditions defining $a_k$ . Of course the first term of $\sigma$ must be 1, and the second term must be either 2 or 3. Let us separately count the number of ways to complete the permutation starting with $1,2$ and with $1,3$ .

In the case that $\sigma$ starts with $1,2$ , if we delete the first term of $\sigma$ and subtract 1 from each remaining term, this gives us a new permutation (call it $\tau$ ) which starts at 1 and has length $k-1$ . This is clearly a bijection between nice permutations $\sigma$ of length $k$ starting with $1,2$ and nice permutations $\tau$ of length $k-1$ starting with 1, so the number of such permutations is $a_{k-1}$ .

In the case that $\sigma$ starts with $1,3$ , we can perform the same bijection, only now the resulting permutation starts with 2 instead of 1. Thus the number of nice permutations starting with $1,3$ is $b_{k-1}$ .

We now know that $a_k = a_{k-1} + b_{k-1}$ . Let's now take a closer look at $b_k$ .

Consider a nice permutation $\sigma$ of length $k \ge 3$ starting with 2. Now $\sigma$ must have a 1 somewhere. We claim it must be at either position 2 or position $k$ : if it is anywhere in between, it will have two neighbours neither of which is 2, but there is only one number besides 2 that is allowed to live next to 1. Let us separately count the cases where $\sigma$ starts with $2,1$ and where $\sigma$ starts with 2 and ends with 1.

If $\sigma$ starts with $2,1$ , then in fact it must start with $2,1,3$ . Now we can delete the first two terms of $\sigma$ and subtract 2 from each of the rest, to get a nice permutation of $\{1,\ldots,k-2\}$ . The number of nice permutations of length $k$ starting with $2,1$ is therefore $a_{k-2}$ .

In the last remaining case, $\sigma$ starts with 2 and ends with 1. It turns out that there is only one nice permutation in this case! Notice that 3 must be positioned next to 1 at the end of the permutation; and that leaves 4 as the only choice to be next to 2. This forcing pattern continues, with 5 being the only choice to place before 3, and 6 being the only choice to place after 4. The unique nice permutation starting with 2 and ending with 1 looks like $2, 4, 6, 8, \ldots, \ldots, 7, 5, 3, 1$ , with even numbers increasing followed by odd numbers decreasing.

This gives a simple formula for $b_k$ : we just have $b_k = a_{k-2} + 1$ . Inserting this into our previous recurrence gives

$a_k = a_{k-1} + a_{k-3} + 1$ , for $k \ge 4$ .

We already know $a_1, a_2, a_3$ so now it's a simple matter to compute $a_4 = 4, a_5 = 6, a_6 = 9$ , and so on, all the way up to $a_{12} = 100, a_{13} = 147, a_{14} = 216, a_{15} = 317$ .

(It is slightly more convenient to work with the recurrence $b_k = b_{k-1} + b_{k-3}$ , starting with $b_3, b_4, b_5$ and using the fact that $a_{15} = b_{17}-1$ .)

Rephrasing the question for easier visualisation: For a row of 15 cells $C_1$ to $C_{15}$ , how many ways are there to visit every cell once by hopping from cell to cell starting from $C_1$ , where you can only hop at most 2 cells?

Let $R_i$ be a row of $i$ cells, where $i \geq 4$ . In order to compute the number of hopping routes for $R_i$ , we count the number of ways to insert $C_i$ into the hopping routes computed for $R_{i-1}$ . To do so, we only need to consider the ways each route for $R_{i-1}$ traverses the last two cells and whether each route ends in $C_{i-1}$ , $C_{i-2}$ or some other cell. Only $C_{i-1}$ and $C_{i-2}$ are relevant since they are the only two cells that can be hopped to or from $C_i$ . Thus, all hopping routes for $R_{i-1}$ can be matched to one of the following patterns:

1. $C_1 - M - C_{i-1} - C_{i-2}$ , where $M$ is an arbitrary permutation of hops. Let this be pattern A.
2. $C_1 - M - C_{i-2} - C_{i-1}$ , where $M$ is an arbitrary permutation of hops. Let this be pattern B.
3. $C_1 - M - C_{i-2} - C_{i-3} - C_{i-1}$ , where $M$ is an arbitrary permutation of hops. Let this be pattern C.
4. $C_1 - M - C_{i-1} - C_{i-2} - N$ or $C_1 - M - C_{i-2} - C_{i-1} - C_{i-3} - N$ , where $M$ and $N$ are arbitrary permutation of hops. Let this be pattern D.

We know that these are all the categories needed because all possible hopping routes for $R_4$ can be allocated to one of these categories, and, since any way to add $C_i$ into any of the above types of hopping routes produces another hopping route that fits into one of the four categories (as shown below), there are no routes that fit into none of the above categories.

Next, we list the ways to add $C_i$ into each of the above categories of hopping routes.

For pattern A, there are two ways: $C_1 - M - C_{i-1} - C_{i-2} - C_{i}$ (pattern C) and $C_1 - M - C_{i-1} - C_{i} - C_{i-2}$ (pattern D).

For pattern B, there are two ways: $C_1 - M - C_{i-2} - C_{i-1} - C_{i}$ (pattern B) and $C_1 - M - C_{i-2} - C_{i} - C_{i-1}$ (pattern A).

For pattern C, there is one way: $C_1 - M - C_{i-2} - C_{i-3} - C_{i-1} - C_{i}$ (pattern B).

For pattern D, there is one way (for each subcategory): $C_1 - M - C_{i-1} - C_{i} - C_{i-2} - N$ or $C_1 - M - C_{i-2} - C_{i} - C_{i-1} - C_{i-3} - N$ (both pattern D) respectively.

Let $A_i$ , $B_i$ , $C_i$ and $D_i$ be the number of hopping routes for $R_i$ corresponding to patterns A, B, C and D respectively. Then:

$A_i=B_{i-1}$
$B_i=B_{i-1}+C_{i-1}$
$C_i=A_{i-1}$
$D_i=D_{i-1}+A_{i-1}$

Now we just need to manually fill a table 12 by 4 cells large (which is very easy since half of the work is just moving values around):

    4   5   6   7   8   9   10  11  12  13  14  15
A   1   1   2   3   4   6   9   13  19  28  41  60
B   1   2   3   4   6   9   13  19  28  41  60  88
C   1   1   1   2   3   4   6   9   13  19  28  41
D   1   2   3   5   8   12  18  27  40  59  87  128

Thus the number of hopping routes for $R_{15}$ is $60+88+41+128=317$ .

Let $a_m$ denote the number of permutation of the set $(1,2,..., m)$ .

We have $a_1=1$ , $a_2=1$ , $a_3=2$ , $a_4=4$ through simple checking.

Now we consider the first few numbers of the permutation for $m>4$ .

Number of permutations of $(1,2,..., m)$ starting with $(1,2)$ , equals $a_{m-1}$

Number of permutations of $(1,2,...,m)$ starting with $(1,3,2,4)$ equals $a_{m-3}$

If the first two numbers are $(1,3)$ , the third number cannot be 4 as if the 4th number is 2, 5 cannot be reached, and if the 4th number is 5, 2 cannot be reached.

Thus the remaining option is for the permutation to start with $(1,3,5)$ . For this sequence, $σ(n)-σ(n-1)=2$ until $σ(n)=m$ or $m-1$ . Else there will two consecutive numbers in the permutation that differs by 1 which separates the remaining numbers into two groups where the difference between any pair of numbers (one from each set) is at least 3. Thus the starting $(1,3,5)$ determines a single permutation.

Thus we have $a_m=a_{m-1}+a_{m-3}+1$ and after some simple calculations, $a_{15}=317$

Let $n_k$ denotes the number of permutations for set with $k+1$ terms, since the first position of any permutation is fixed as 1. For the value of $n_k$ , there are following three cases.

1. First position is fixed as 1. Second position may be 2. Then the remaining permutation equals to $n_{k-1}$ .

2. Second position may be 3. The third position may be 2. Then the fourth position must be 4. Then the remaining permutation equals to $n_{k-3}$ .

3. Second position may be 3. If the third position is not 2, then third position must be 5 only, because if it is 4 there will be no place for 2. As such, we can suppose without loss of generality that there is only one special case whereby the permutation is {1,3,5,7,9,11,13,15,14,12,10,8,6,4,2}

In conclusion, $n_k=n_{k-1}+n_{k-3}+1$ . It is obvious that $n_1=1$ and $n_2=2$ and $n_3=4$ . Hence, you eventually get $n_{14}=317$ .

Since the first position of the permutation is set to be 1, the second position must be either 2 or 3. If we put 2, the trend continues with placing either 3 or 4 in the next place. If we put 3 in the second position, the third position must be filled with 2 or 5. (not 4 because we are not able to place either 2 or 5 in the following positions)

With this principle in mind, (i.e. it cannot be permutated in such a way that n is followed by n+2 and n+3), we first consider drawing a small branch of a tree diagram for this permutation. 1-2-3-4-...-11-12-13... the last two positions can be filled with

a. 14-15

b. 15-14

we can see there are two cases if we start the permutation in a strictly increasing order until number 13.

now we consider the case of starting the permutation with 1 to 12,

there another two possible ways of arranging it:

a. 14-13-15

b. 14-15-13

starting from 1 to 11, in the 12th position, we can choose to place 12 (repeating the four cases above) or 13,

so we have

a. 13-15-14-12 (keep in mind the principle we have mentioned, it also means once we start writing the permutation in a way like 1-3-5-... we must continue writing odd numbers 1-3-5-7-9-11-13-15 then 14-12-... and return to 2)

b. 13-12-14-15

enough of drawing, we can now do some simple thinking and calculation, if we write 1 to 10 consecutively, the new ways (not counting the aforementioned ones) must continue with 12,

a. we can write 12-14-... (as discussed above, this only leads to only one way of arrangement)

b. or we write 12-11-13.. (notice that we can regard this permutation as starting from 1 to 13, and we have discovered that starting from 1 to 13 gives two different ways of permutating it, so there are two ways of doing so)

Now we have realized the trend, consider 1-2...-8-9-11,

a. goes to 13, 1 way of arranging it

b. goes back to 10 and then 12, regard it as the sequence 1-2-...11-12, we get 4 permutations

so we can add all the possible permutations together,

2+2+2+(2+1)+(2+2+1)+(2+2+2+1)+(2+2+2+2+1)+(2+2+2+2+1+2+2+1)+...

since the number is rather small, i did not find the general expression for it, adding until the last term (1-3-2-4-...), which is 100+1,

we get the answer 2+2+2+(2+1)+(4+1)+(6+1)+(9+1)+(14+1)+(21+1)+(31+1)+(46+1)+(68+1)+(100+1)=317,

P.S: Sorry I could not explain the idea really clearly maybe because I am quite weak in mathematical expression and English language.. anyway one can find the pattern that from the fourth term onward, the new permutations for nth term are the sum of the first term to (n-3)th term plus 1. And the sequence ends when the permutation starts with 1-3-2-4 which is the last case we need to consider.

The key to the counting of permutations satisying the conditions is the placement of the maximum element 15 in the set (since the minimum is already fixed at position 1).

We define an auxiliary function f(n): given n+2 successive integers, f(n) is the number of ways to place them in such an order that the minimum comes first, the maximum comes last, and the difference between any two direct neighbours is at most 2.

We will also use the inverse mapping of $\sigma$ : $\sigma^{-1}(n) = m$ if and only if $\sigma(m) = n$ . For example, $\sigma^{-1}(15)$ indicates the position of the number 15.

If $\sigma^{-1}(15) = 15$ , the numbers 2 to 14 are to be placed between the fixed numbers 1 and 15. The number of permutations for this case is f(13).

Since the maximum difference between two neighbours is 2, the least position 15 can be at is 8, which makes the sequence start 1, 3, 5, 7, 9, 11, 13, 15... and after that point, only the even numbers are left, so it continues 14, 12, 10, 8, 6, 4, 2.

If $\sigma^{-1}(15) < 15$ , the number 15 has two neighbours, and they must be the numbers 14 and 13. We get two cases: A) the subsequence 13, 15, 14, and B) the subsequence 14, 15, 13.

Given the placement of 15 and the selection of one the above cases, the numbers at positions larger than $\sigma^{-1}(15)$ are uniquely determined. We can use this process: Because starting with the neighbour of the higher of the end numbers N (14 above), the number N-1 and all higher numbers have already been placed, so the neighbour must be N-2. We can continue this until position 15 is filled. If $\sigma^{-1}(15) = m$ , there are 15-m positions above m, which are now filled, and 15-m below, the lowest being M. The highest unfilled position is thus 2m-16. In case B, the number at that position is determined too, namely M-2, since M-1 (the other possible candidate for a neighbour to M) is at position 15.

Thus, for $\sigma^{-1}(15) = m$ , the highest unfilled position is 2m-16 (case A) or 2m-17 (case B), for all m from 14 down to 9. Given that $\sigma(1) = 1$ , we have 2m-17 and 2m-18 unfilled positions, respectively.

For m = 8, we got above that there is one possible permutation. For m = 15, there are f(13). For m from 9 to 14, we have all the values f(0), f(1), f(2), etc. up to f(11). All that remains is to compute the function f(n).

f(0) means there is nothing to place, so f(0) = 1. f(1) means one single number is placed, so f(1) = 1. With two positions, the numbers can be placed in order, or in reverse order, so f(2) = 2. For n > 2, we have two cases for the number at the first position: either the minimum unplaced number P, or P+1 (since we have the number P-1 just before). In the case P+1, the next number must be P and the next number after that must be P+2. The number of possibilities for the two cases are thus f(n-1) and f(n-3), respectively. Therefore f(n) = f(n-1) + f(n-3), and we can compute all the values of f that we need: f(0) to f(13) are: 1 1 2 3 4 6 9 13 19 28 41 60 88 129. Adding 1 (from m = 8), f(13) and f(0) to f(11), we get the answer of the problem, namely 317.

Let $P\left(x\right)$ denote the number of permutations of a set of $x$ consecutive integers that satisfy these conditions. We are trying to find $P\left(15\right)$ . To do this, we can develop a recursive function.

Begin with the number $1$ in a tree diagram. $1$ can branch off to $2$ or $3$ , anything else would not satisfy the conditions. In the branch to $2$ , we are left with a set of consecutive integers $\{2,3,\dots,15\}$ . So branch has $P\left(x-1\right)=P\left(15-1\right)$ permutations.

For the branch to $3$ , there is a digit skipped over. From this, we must force the set to be of consecutive integers by expanding the tree more. $3$ can branch to $1$ , $2$ , $4$ , and $5$ . It cannot branch to $1$ because $1$ has already been used. It also cannot branch to $4$ either because there would be no way to return to $2$ . Thus, it can only branch to $2$ and $5$ .

If $3$ branches to $2$ , the $2$ must branch to $4$ , which is $P\left(x-3\right)$ permutations. The only way for $3$ to branch to $5$ is if a path is travelled along the odd numbers and back down through the even numbers ( $\{3,5,7,\dots,15,14,12,\dots,4,2\}$ ), which is only $1$ permutation.

Thus, we can give the recursive relation of $P\left(x\right) = P\left(x-1\right) + P\left(x-3\right) + 1$ . For this recursive function to work, there must be some base cases. Case 1: $x=1$ . The only permutations of a set with size $1$ are the only number in the set. Case 2: $x=2$ . There is only $1$ way to arrange the second digit such that $\sigma\left(1\right) = 1$ . Case 3: $x=3$ . Consider an arbitrary set of $3$ consecutive integers, $\{1,2,3\}$ for simplicity. The only possible permutations satisfying the conditions are $\{1,2,3\}$ and $\{1,3,2\}$ . This is true for all sets of size $3$ , so the number of permutations is $2$ .

Thus, $P\left(x\right) = \begin{cases} 1, & \text{if } x = 1 \text{ or } x = 2 \\ 2, & \text{if } x = 3 \\ P\left(x-1\right)+P\left(x-3\right)+1, & \text{else} \end{cases}$

Solving for $x=15$ yields $P\left(15\right)=317$ .

Let f(N) be the number of permutations of {1..N} such that σ(1)=1, ∣σ(n)−σ(n−1)∣≤2 for 2≤n≤N. We can find a recurrence for f(N).

If we have σ(2)=2, then it is as if we have 1 number less to fill and 2 is effectively the new 1. So we can fill the remaining positions in f(N-1) ways.

If we have σ(2)=3, σ(3)=2, σ(4)=4, then, similar to the earlier case, we have the option of filling the remaining blanks in f(N-3) ways.

Other than these, there is only one option. It is σ(2)=3, σ(3)=5, σ(4)=7 ... σ(n-2)=6, σ(n-1)=4, σ(n)=2

Combining, we obtain : f(N) = f(N-1) + f(N-3) + 1 Using the base cases f(1)=f(2)=1,f(3)=2, we can iteratively calculate f(15)=317.

We call a permutation on the set $\{1, 2, \ldots , k\}$ legal if it satisfies $\sigma(1)=1, \lvert \sigma (n) - \sigma (n-1) \rvert \leq 2$ for $2 \leq n \leq k$ . Let $p(k)$ be the number of legal permutations on the first $k$ integers. We can calculate the following: $p(1) = 1, p(2) = 1$ and $p(3) = 2$ .

Claim: $p(k) = p(k-1) + p(k-3) +1$ for $k \geq 4$ .

Given a legal permutation on $k$ integers, we have the following three cases.

Case 1: $\sigma(2) =2$ . We can create a bijection with a legal permutation on $k-1$ integers by setting $\sigma'(m)=\sigma(m+1)-1$ for $m=1$ to $k-1$ . Thus, there are $p(k-1)$ ways.

Case 2: $\sigma (2) = 3$ and $\sigma (3) = 2$ . This forces $\sigma (4) = 4$ . We can create a bijection with a legal permutation on $k-3$ integers by setting $\sigma'(m) = \sigma(m+3)-3$ for $m=1$ to $k-3$ . Thus, there are $p(k-3)$ ways.

Case 3: $\sigma (2)=3$ and $\sigma(3)\neq 2$ . Consider the value of $i$ such that $\sigma(i)=2$ . If $i \neq k$ , then $\sigma (i-1)$ and $\sigma(i+1)$ must both be 4, which contradicts the permutation assumption. Thus $\sigma (k)=2, \sigma (k-1)=4$ . If $k\geq 5$ , then $\sigma(3)=5$ is the only possiblity. If $k\geq 6$ , then $\sigma(k-3)=6$ is the only possibility. We continue until we reach the midpoint and the only possible permutation is $(1, 3, 5, 7, \ldots, 6, 4, 2)$ . Thus, there is only 1 way.

This establishes the claim. We can calculate directly that $p(15) = 317$ . While the recurrence relation in the claim can be solved to get a closed form for $p(n)$ , it is would be quicker to evaluate $p(15)$ by using the recurrence relation since the characteristic equation doesn't have nice roots.

In PARI/GP:

ok(v)=my(u=vecsort(v,,8));#u==#v&&u[1]==1&&u[#u]<16
step(V)=my(U=List());for(i=1,#V,my(v=V[i],m=v[#v],u);for(j=m-2,m+2,u=concat(v,j);if(ok(u),listput(U,u))));Vec(U)
v=[[1]];for(i=2,15,v=step(v));#v

Let $C(n)$ denote the answer to the problem for the set $\{1, 2, 3, \ldots, n\}$ . For $n>3$ , we can use the following argument:

Obviously, $\sigma(2)$ is either 2 or 3. If $\sigma(2)=2$ , the problem is reduced to the problem for $n-1$ , so there are $C(n-1)$ permutations in this case.

If $\sigma(2)=3$ , then $\sigma(3)$ is either 2 or 5. If $\sigma(3)=2$ , then we must have $\sigma(4)=4$ , so the problem is reduced to the problem for $n-3$ , giving us $C(n-3)$ permutations in this case. If $\sigma(3)=5$ , it is not difficult to see that there is only one possible permutation, namely the permutation with all the odd numbers in increasing order, followed by all the even numbers in decreasing order.

Combining our cases, we see that $C(n)=C(n-1)+C(n-3)+1$ . We can use this recursion (starting with $C(1)=1, C(2)=1, C(3)=2$ ) to eventually find that $C(15)=\boxed{317}$ .