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?

  • $\begingroup$ 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$.) $\endgroup$ – Thomas Andrews Apr 3 '13 at 15:46
  • 1
    $\begingroup$ No, $a_{n+1} \ne a_1$. To avoid misunderstanding, I've changed from $i=1,...,n$ to $i=1,...,n-1$ $\endgroup$ – JosephConrad Apr 3 '13 at 17:45

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.

  • $\begingroup$ +1 Thanks, pretty nice solution! I've tried to use inclusion-exclusion method, but using this approach it looks much more elegant. $\endgroup$ – JosephConrad Apr 3 '13 at 17:48

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.