5
$\begingroup$

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.

$\endgroup$
1

1 Answer 1

4
$\begingroup$

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$.)

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

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.