4
$\begingroup$

Recall that the number or Derangements of $1,2,\dots,n$ is a permutation $p$ such that $p(i) \neq i$ for all $i$. We can express it with the recurrence $D_n=(n-1)(D_{n-1}+D_{n-2})$ or by the closed formula $$D_n =\sum_{i=0}^n (-1)^i \frac{n!}{i!}$$

Now we consider the number of permutations of $1,2,\dots, n,n+1$ such that for all $1\leq i \leq n$ (not $n+1$), $p(i)\neq i$, but also $p(n+1) \neq n$. We need to express this number using $D_n$s.

I was thinking of first counting the number of permutations without the additional condition $p(n+1) \neq n$ and received using inclusion-exclusion

$$\sum_{r=0}^n (-1)^r \binom{n}{r}(n+1-r)! = \sum_{r=0}^n (-1)^r \frac{n!}{r!}(n+1-r) =$$ $$\sum_{r=0}^n (-1)^r \frac{(n+1)!}{r!}- \sum_{r=1}^n (-1)^r \frac{n!}{(r-1)!}=$$ $$\sum_{r=0}^n (-1)^r \frac{(n+1)!}{r!}- n\sum_{r=0}^{n-1} (-1)^{r+1} \frac{(n-1)!}{r!}=$$ $$=D_{n+1}+nD_{n-1}$$

Now we need to subtract from this the number of permutations when $p(n+1)=n$, which I wasn't able to count.

Thanks in advance

$\endgroup$
  • $\begingroup$ The number of permutations of $\{1,\ldots,n+1\}$ with $p(n+1)=n$ is simply the number of permutations of $\{1,\ldots,n\}$; compose any such permutation with the transposition $(n\ n+1)$ yields a bijection between these sets of permutations. $\endgroup$ – Servaes Dec 15 '18 at 9:42
  • $\begingroup$ But in our case, we count the permutations with $p(i)\neq i$, are you sure there is such bijection? Because when $n+1$ takes $n$'s place, we dont have to worry about $p(n) \neq n$ anymore. $\endgroup$ – Theorem Dec 15 '18 at 9:46
  • $\begingroup$ Ah, so you mean to count the number of derangements with $p(n+1)\neq n$? I only read your question at a glance, and commented on the last sentence. $\endgroup$ – Servaes Dec 15 '18 at 9:49
  • $\begingroup$ Yes, I didn't say exactly derangements because that would imply $p(n+1)\neq n+1$, but it is very similar. $\endgroup$ – Theorem Dec 15 '18 at 9:50
  • $\begingroup$ In a derangement, $n+1$ is as likely to go to $n$ as to any given element of $\{1,\ldots,n\}$. $\endgroup$ – Lord Shark the Unknown Dec 15 '18 at 10:30
1
$\begingroup$

Call a permutation $\sigma$ of $\{1,\ldots,n+1\}$ good if $\sigma(i)\neq i$ for all $1\leq i\leq n$ and and $\sigma(n+1)\neq n$.

Let $\sigma$ be a good permutation, and let $a:=\sigma(n+1)$ and $b:=\sigma^{-1}(n+1)$, so that $a\neq n$. If $a\neq b$ then the permutation $(a\ n+1)\sigma$ fixes $n+1$ and is a derangement of $\{1,\ldots,n\}$. If $a=b$ then $(a\ n+1)\sigma$ fixes $a$ and $n+1$, and is a derangement of $\{1,\ldots,n\}\setminus\{a\}$.

Conversely, for any derangement $\sigma$ of $\{1,\ldots,n\}$ and any $a\in\{1,\ldots,n+1\}$ with $a\neq n$ the composition $(a\ n+1)\sigma$ is good. Also, for any $a\in\{1,\ldots,n-1\}$ and any derangement $\sigma$ of $\{1,\ldots,n\}\setminus\{a\}$ the composition $(a\ n+1)\sigma$ is good.

This shows that the number of good permutations is $nD_n+(n-1)D_{n-1}$, where $D_m$ denotes the number of derangements of $\{1,\ldots,m\}$.

$\endgroup$
1
$\begingroup$

These kind of problems (permutations with forbidden positions) can be elegantly solved using rook numbers/polynomials:

Let $P \subseteq \{1, \ldots, n\}^2$ be the diagram of forbidden positions. The number of permutations $p \in S_n$ such that $(i,p(i)) \notin P$ for all $i = 1, \ldots, n$ is given by $$\sum_{k=0}^n (-1)^k(n-k)!r_k$$ where $r_k$ is the number of ways to place $k$ nonattacking rooks on the diagram $P$.

In our case the diagram e.g. for $n=4$ (the board is then $5 \times 5$) is given by:

enter image description here

$0$ rooks can be placed in one way on $P$. To place $k$ rooks on $P$, one can place a rook on one of the two positions in the last column of $P$ in $2$ ways and then place $k-1$ rooks on $n-1$ remaining positions, or one can just place all $k$ rooks in the first $n-1$ columns, ignoring the last one. Hence $$r_k = \begin{cases} 1, \text{ if }k=0\\ 2{n-1 \choose k-1} + {n-1 \choose k}, \text{ if }k \ge 1 \end{cases} = \begin{cases} 1, \text{ if }k=0\\ {n \choose k} + {n-1 \choose k-1}, \text{ if }k \ge 1 \end{cases}$$

Therefore the result is \begin{align} \sum_{k=0}^n (-1)^k(n-k)!r_k &= \sum_{k=0}^n (-1)^k(n-k)!{n \choose k} + n! + \sum_{k=1}^n (-1)^k(n-k)!{n-1 \choose k-1} \\ &= D_n + n! - \sum_{j=0}^{n-1} (-1)^j((n-1)-j)!{n-1 \choose j} \\ &= D_n + n! - D_{n-1} \end{align}

$\endgroup$
  • $\begingroup$ Is there no simple solutions without pulling any big guns? The problem shouldn't be this complicated and I think I'm missing a key principle. (In addition I'm not sure the solution you achieved is correct) $\endgroup$ – Theorem Dec 15 '18 at 11:23

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.