# permutations of $\{1,2,\cdots , n \}$ with some restriction

Problem: I am trying to calculate the number of permutations $f(n)$ of $\{1,2,\cdots , n \}$ such that there aren't any adjacent digits in which the right one is greater than the left one by exactly 1 increment.

Example: For $n=3$ we have:

$$132, 213, 321$$ Hence $f(3)=3$. It can be calculated that $\ f(4)=11, \ f(5)=53$

Ideas: It seems to be inclusion exclusion principle would work, but there are too many cases to count. I tried to find a recurrence relation, but couldn't do it either. I am wondering that this problem should have risen somewhere. If anyone can give me some reference, I will certainly appreciate it.

• Oct 27, 2014 at 22:40

A recurrence relation isn’t too hard. Consider an acceptable permutation $\pi$ of $[n+1]$. If you remove the $n+1$, there are two general possibilities for the resulting permutation of $[n]$.

• It may be acceptable.
• It may be unacceptable, but only because the number that was immediately to the left of $n+1$ in $\pi$ is one less than the number that was immediately to the right of $n+1$ in $\pi$.

There are $f(n)$ acceptable permutations of $[n]$, and $n+1$ can be inserted into any of them in any of the $n$ slots that are not immediately to the right of the $n$, so these account for $nf(n)$ acceptable permutations of $[n+1]$. It only remains to count the permutations of $[n]$ that are unacceptable in exactly one position.

Suppose that $\sigma$ is such a permutation, and in it $k$ and $k+1$ are adjacent in that order. Remove $k+1$ and decrease every remaining element of $\sigma$ that is greater than $k$ by $1$; the result is an acceptable permutation of $[n-1]$. Conversely, if you start with an acceptable permutation of $[n-1]$, pick any $k$ in it, increase by $1$ every element that is greater than $k$, and insert $k+1$ immediately to the right of $k$, you get a permutation of $[n]$ that is unacceptable in exactly one position. There are $n-1$ choices for $k$, so there are $(n-1)f(n-1)$ permutations of $[n]$ that are unacceptable in exactly one position.

Putting the pieces together, we see that $f(n+1)=nf(n)+(n-1)f(n-1)$. (This differs from the recurrence given for OEIS A000255, mentioned in the comments, because the indexing is off by $1$.)

• okay this one perfect recurrence, what I couldnt handle was the second part, thanks Oct 28, 2014 at 12:26
• @iamvegan: You’re welcome. Oct 28, 2014 at 19:50