# Number of permutations of numbers where the difference between each number and the one on the left is different than 1

I've been struggling with this for a long time now, and I can't find a plausible logic to solve it.

Lets say that you have the numbers $1, 2, 3, \ldots, n$. How many are the possible permutations of these numbers: $a_1, a_2, a_3, \ldots a_n$ - is a permutation, where $a_k - a_{k-1} \neq 1$, for $k$ going from $1$ to $n$?

In other words, when $n = 6$: $123456$ is not an acceptable permutation as $5 - 4 = 1$ or $6 - 5 = 1$, etc.

On the other hand: $654321$ is acceptable, as neither of the numbers is bigger with $1$ than the one on its left.

I've managed to, I think, find the number of acceptable permutations, where as we fill the next position, we never take the biggest number of the remaining, so the result is $(n-1)(n-2)(n-3) \cdots 1$. But this is obviously not the full amount of acceptable permutations.

What is the logic behind this task? I'm pretty sure that I'm going the wrong way with my logic.

• This appears to be the answer. – David Dec 5 '17 at 2:20
• Please read this tutorial on how to typeset mathematics on this site. – N. F. Taussig Dec 5 '17 at 11:32

Let $u_n$ be the number of permutations of $\{1,\ldots,n\}$ having this property. All such permutations can be obtained in a unique way by inserting $n$ into a permutation of $\{1,\ldots,n-1\}$. There are two cases.

1. The shorter permutation never has $a_k-a_{k-1}=1$. There are $u_{n-1}$ such permutations and then $n-1$ spots to place $n$ (anywhere except the place after $n-1$).

2. The shorter permutation has $a_k-a_{k-1}=1$ for exactly one value of $k$. The number of choices for $k$ is $n-2$; the number of permutations is $u_{n-2}$, see below for proof; and there is only one placement for $n$, as it must go between $a_k$ and $a_{k-1}$ in order to split the pair.

Therefore the required number satisfies $$u_n=(n-1)u_{n-1}+(n-2)u_{n-2}\ .$$ You can use this, with initial conditions $u_1=u_2=1$, to find any value you wish of $u_n$; unfortunately there does not seem to be any particularly simple formula giving $u_n$ directly in terms of $n$.

Lemma. Suppose that $m$ is given, $1\le m\le n-2$. The number of permutations of $\{1,\ldots,n-1\}$ in which $l$ is followed by $l+1$ if and only if $l=m$ is $u_{n-2}$.

Proof. In such a permutation $m+1$ cannot be followed by $m+2$. So if we delete $m+1$ then $l$ is never followed by $l+1$ and $m$ is not followed by $m+2$. So we have a permutation of the list $$(1,\ldots,m,m+2,\ldots,n-1)$$ in which no element is followed by the next element from the original list. The number of such is $u_{n-2}$, and the construction is reversible, so the proof is complete.

• Did you notice the relation between $u_{n}$ and the number of derangements $D_{n+1}$? It might have an interesting combinatorial interpretation, too. – Jack D'Aurizio Dec 5 '17 at 18:38
• @JackD'Aurizio No I didn't, but I did notice that the OEIS entry gives connections with subfactorials, which are connected with derangements. (It gives a lot of other relations too.) – David Dec 5 '17 at 22:33

As an addendum to David's answer, given $$u_n = (n-1)u_{n-1}+(n-2)u_{n-2},\qquad u_1=1,u_2=1$$ we may set $u_n=(n-1)! a_n$ to get $$a_{n+1} - a_{n} = \frac{a_{n-1}}{n},\qquad a_1=1,a_2=1$$ and recognize that derangements are involved: $$\boxed{ u_n = \frac{D_{n+1}}{n} = \frac{(n+1)!}{n}\sum_{k=0}^{n+1}\frac{(-1)^k}{k!}.}$$