# Number of permutations $\langle a_1,\ldots,a_n\rangle$ of $\{ 1,\ldots ,n \}$ with $a_{i+1} - a_i \ne 1$

Prove that for $$n>0$$, the number of permutations $$\langle a_1,\ldots,a_n\rangle$$ of the set $$\{ 1,\ldots ,n \}$$, where $$a_{i+1} - a_i \ne 1$$ for $$i = 1, \ldots, n-1$$ is equal to:

$$D_n + (n-1)D_{n-2} +(-1)^{n-1},$$

where $$D_n$$ is the number of $$n$$-permutations with no fixed points.

I have tried to cope with this using inclusion-exclusion rule:

$$A_i = (n-1)(n-2)! = (n-1)!$$

and so on. But for bigger products it is much more complicated. Any hints?

• When you say "for $i=1,\dots,n$..."does $a_{n+1}=a_1$? Also, does this allow $a_{i+1}$ to be $1$ and $a_i$ to be $n$? (I'm guessing not for the latter, because I think then the number would be just $D_n$.) – Thomas Andrews Apr 3 '13 at 15:46
• No, $a_{n+1} \ne a_1$. To avoid misunderstanding, I've changed from $i=1,...,n$ to $i=1,...,n-1$ – JosephConrad Apr 3 '13 at 17:45

We will make use of two key recurrences for derangements, i.e. $$D_n = nD_{n-1} + (-1)^n$$ $$D_n = (n-1)(D_{n-1} + D_{n-2})$$ Let me denote the number of desired permutations as $\alpha_n$. First note that your equation is in fact equal to $$\alpha_n = D_n + (n-1)D_{n-2} + (-1)^{n-1} = D_n + D_{n-1}$$ Now let us try to generate a recurrence for $\alpha_n$.
First consider a valid permutation on $n$ letters. If we remove element $n$ then we are either left with a valid permutation on $n-1$ letters or a permutation with exactly one "ascent", i.e. exactly one $i$ such that $a_{i+1} - a_i = 1$. Conversely, it's easy to see that given any valid permutation on $n-1$ letters, there are exactly $n-1$ positions to insert $n$ to complete a valid permutation on $n$ letters. We can insert $n$ in any of the gaps except behind $n-1$. Likewise, given any permutation with one ascent we can insert $n$ in exactly one location to separate the ascent. Therefore we have the recurrence $$\alpha_n = (n-1)\alpha_{n-1} + \beta_{n-1}$$ where $\beta_{n-1}$ is the number of "one ascent" permutations on $n-1$ letters.
Now we seek to relate $\alpha$ and $\beta$. Given $n$ letters, in order to construct a permutation with one ascent, we must first choose a pair of consecutive numbers to be together in our permutation. There are precisely $n-1$ such pairs. Now regarding these consecutive numbers as a single element, we may relabel as necessary to consider a permutation on $n-1$ letters. The original permutation on $n$ elements will have one ascent if and only if the new permutation on $n-1$ elements has no ascents.
For example, consider a permutation on $\{1,2,3,4,5,6\}$. We first choose a pair, say $(2,3)$. Say our original permutation is $$\pi=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 \\ 5 & 4 & 6 & 2 & 3 & 1\end{pmatrix}$$ then we can collapse $(2,3)\mapsto 2$ and relabel $4\mapsto 3$, $5\mapsto 4$, $6 \mapsto 5$, to get a permutation on $5$ letters $$\pi' = \begin{pmatrix}1&2&3&4&5\\4&3&5&2&1\end{pmatrix}$$ You can check that this process is bijective. We therefore have $$\beta_n = (n-1)\alpha_{n-1}$$ which gives our recursion as $$\alpha_n = (n-1)\alpha_{n-1} + (n-2)\alpha_{n-2}$$ with initial conditions $\alpha_1 = 1$ and $\alpha_2 = 1$. It's quite easy to show at this point that $\alpha_n = D_n + D_{n-1}$ satisfies the above recurrence.