Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
A bit of a backwards way of doing this. Perhaps there is a more direct approach but for now let's try this.
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.
