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 }$$ The last sum should look familiar: $$e^x=\sum_{k=0}^\infty {1\over k!}x^k.$$ Substituting $x=-1$ gives $$e^{-1} = \sum_{k=0}^\infty {1\over k!}(-1)^k.$$ 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!},$$ and when $n$ is bigger than 6, this is quite close to $$e^{-1} \approx 0.3679.$$ 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. First, note that when
$n=0$, we have $D_0=0!(-1)^0{1\over 0!}=1$. "Derangements of the
empty set'' doesn't really make sense, but it is useful to adopt the
convention that $D_0=1$.

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})$. Starting with $D_0=1$ and $D_1=0$, this gives $D_2=(1)(0+1)=1$ and $D_3=(2)(1+0)=2$, both of which are easy to check directly.

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
}$$
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}.$$
If this continues, we should get to
$$D_n=nD_{n-1}+(-1)^{n-2}D_{2}+(-1)^{n-1}(2)D_{1}.$$
Since $D_2=1$ and $D_1=0$, this would give
$$D_n=nD_{n-1}+(-1)^n,$$
since $\ds (-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$$

There are many similar problems.

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

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)!}. $$ Note that the limits on the two sums are not identical.

## Exercises 2.2

**Ex 2.2.1**
Prove that $\ds D_n=nD_{n-1}+(-1)^n$ when $n\ge2$, by
induction on $n$.

**Ex 2.2.2**
Prove that $D_n$ is even if and only if $n$ is odd.

**Ex 2.2.3**
Provide the missing details for
example 2.2.1.
What is $\ds\lim_{n\to\infty} {Q_n\over n!}$?

**Ex 2.2.4**
Find the number of permutations of $1,2,\ldots,8$ that have no
odd number in the correct position.

**Ex 2.2.5**
Find the number of permutations of $1,2,\ldots,8$ that have at least one
odd number in the correct position.

**Ex 2.2.6**
How many permutations of $[n]$ have exactly $k$ numbers in
their correct positions?

**Ex 2.2.7**
Give a combinatorial proof that
$$n!=\sum_{k=0}^n {n\choose k}D_{n-k}.$$

**Ex 2.2.8**
A small merry-go-round has 8 seats occupied by 8
children. In how many ways can the children change places so that no
child sits behind the same child as on the first ride? The seats do
not matter, only the relative positions of the children.

**Ex 2.2.9**
On the way into a party everyone checks a coat and a bag at the door. On
the way out, the attendant hands out coats and bags randomly. In how many ways
can this be done if

(a) No one gets either their own coat or their own bag?

(b) One may get one's own coat, or bag, but not both.

**Ex 2.2.10**
Suppose $n$ people are seated in $m\ge n$ chairs in a
room. At some point there is a break, and everyone leaves the
room. When they return, in how many ways can they be seated so that no
person occupies the same chair as before the break?