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.

  • 4
    $\begingroup$ This appears to be the answer. $\endgroup$ – David Dec 5 '17 at 2:20
  • $\begingroup$ Please read this tutorial on how to typeset mathematics on this site. $\endgroup$ – 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.

  • $\begingroup$ Did you notice the relation between $u_{n}$ and the number of derangements $D_{n+1}$? It might have an interesting combinatorial interpretation, too. $\endgroup$ – Jack D'Aurizio Dec 5 '17 at 18:38
  • $\begingroup$ @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.) $\endgroup$ – 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!}.} $$


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.