# 2.2: Forbidden Position Permutations

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

Suppose we shuffle a deck of cards; what is the probability that no card is in its original location? More generally, how many permutations of $$[n]=\{1,2,3,\ldots,n\}$$ have none of the integers in their "correct'' locations? That is, 1 is not first, 2 is not second, and so on. Such a permutation is called a derangement of $$[n]$$.

Let $$S$$ be the set of all permutations of $$[n]$$ and $$A_i$$ be the permutations of $$[n]$$ in which $$i$$ is in the correct place. Then we want to know $$|\bigcap_{i=1}^n A_i^c|$$.

For any $$i$$, $$|A_i|=(n-1)!$$: once $$i$$ is fixed in position $$i$$, the remaining $$n-1$$ integers can be placed in any locations.

What about $$|A_i\cap A_j|$$? If both $$i$$ and $$j$$ are in the correct position, the remaining $$n-2$$ integers can be placed anywhere, so $$|A_i\cap A_j|=(n-2)!$$.

In the same way, we see that $$|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|=(n-k)!$$. Thus, by the inclusion-exclusion formula, in the form of Equation 2.1.1,

\eqalign{ |\bigcap_{i=1}^n A_i^c|&=|S|+\sum_{k=1}^n (-1)^k{n\choose k}(n-k)!\cr &=n!+\sum_{k=1}^n (-1)^k{n!\over k!(n-k)!}(n-k)!\cr &=n!+\sum_{k=1}^n (-1)^k{n!\over k!}\cr &=n!+n!\sum_{k=1}^n (-1)^k{1\over k!}\cr &=n!\,\Bigl(1+\sum_{k=1}^n (-1)^k{1\over k!}\Bigr)\cr &=n!\,\sum_{k=0}^n (-1)^k{1\over k!}.\cr }\nonumber

The last sum should look familiar: $e^x=\sum_{k=0}^\infty {1\over k!}x^k.\nonumber$ Substituting $$x=-1$$ gives $e^{-1} = \sum_{k=0}^\infty {1\over k!}(-1)^k.\nonumber$ The probability of getting a derangement by chance is then ${1\over n!}n!\,\sum_{k=0}^n (-1)^k{1\over k!} =\sum_{k=0}^n (-1)^k{1\over k!},\nonumber$ and when $$n$$ is bigger than 6, this is quite close to $e^{-1} \approx 0.3678.\nonumber$ So in the case of a deck of cards, the probability of a derangement is about 37%.

Let $$D_n=n!\,\sum_{k=0}^n (-1)^k{1\over k!}$$. These derangement numbers have some interesting properties. The derangements of $$[n]$$ may be produced as follows: For each $$i\in\{2,3,\ldots,n\}$$, put $$i$$ in position 1 and 1 in position $$i$$. Then permute the numbers $$\{2,3,\ldots,i-1,i+1,\ldots n\}$$ in all possible ways so that none of these $$n-2$$ numbers is in the correct place. There are $$D_{n-2}$$ ways to do this. Then, keeping 1 in position $$i$$, derange the numbers $$\{i,2,3,\ldots,i-1,i+1,\ldots n\}$$, with the "correct'' position of $$i$$ now considered to be position 1. There are $$D_{n-1}$$ ways to do this. Thus, $$D_n=(n-1)(D_{n-1}+D_{n-2})$$.

We explore this recurrence relation a bit:

\eqalignno{ D_n&=nD_{n-1}-D_{n-1}+(n-1)D_{n-2}&(*)\cr &=nD_{n-1}-(n-2)(D_{n-2}+D_{n-3})+(n-1)D_{n-2}\cr &=nD_{n-1}-(n-2)D_{n-2}-(n-2)D_{n-3}+(n-1)D_{n-2}\cr &=nD_{n-1}+D_{n-2}-(n-2)D_{n-3}&(*)\cr &=nD_{n-1}+(n-3)(D_{n-3}+D_{n-4})-(n-2)D_{n-3}\cr &=nD_{n-1}+(n-3)D_{n-3}+(n-3)D_{n-4}-(n-2)D_{n-3}\cr &=nD_{n-1}-D_{n-3}+(n-3)D_{n-4}&(*)\cr &=nD_{n-1}-(n-4)(D_{n-4}+D_{n-5})+(n-3)D_{n-4}\cr &=nD_{n-1}-(n-4)D_{n-4}-(n-4)D_{n-5}+(n-3)D_{n-4}\cr &=nD_{n-1}+D_{n-4}-(n-4)D_{n-5}.&(*)\cr }\nonumber

It appears from the starred lines that the pattern here is that $D_n=nD_{n-1}+(-1)^kD_{n-k}+(-1)^{k+1}(n-k)D_{n-k-1}.\nonumber$ If this continues, we should get to $D_n=nD_{n-1}+(-1)^{n-2}D_{2}+(-1)^{n-1}(2)D_{1}.\nonumber$ Since $$D_2=1$$ and $$D_1=0$$, this would give $D_n=nD_{n-1}+(-1)^n,\nonumber$ since $$(-1)^n=(-1)^{n-2}$$. Indeed this is true, and can be proved by induction. This gives a somewhat simpler recurrence relation, making it quite easy to compute $$D_n$$.

$\bullet\quad\bullet\quad\bullet\nonumber$

There are many similar problems.

Example $$\PageIndex{1}$$

How many permutations of $$[n]$$ contain no instance of $$i$$ followed by $$i+1$$?

Solution

By a similar use of the inclusion-exclusion formula, it turns out that this is $Q_n=n!\,\sum_{k=0}^{n-1} (-1)^k{1\over k!}+ (n-1)!\,\sum_{k=1}^{n-1} (-1)^{k-1} {1\over (k-1)!}. \nonumber$ Note that the limits on the two sums are not identical.