derangement

Let $S_n$ be the symmetric group of order $n\ge 1$. A permutation $\varphi \in S_n$ without a fixed point (that is, $\varphi (i)\ne i$ for any $i\in \{1,\mathrm{\dots },n\}$) is called a derangement.

In combinatorial theory, one is usually interested in the number $d(n)$ of derangements in $S_n$. It is clear that $d(1)=0,d(2)=1$, and $d(3)=2$. It is also not difficult to calculate $d(n)$ for small $n$. For general $n$, one can appeal to the principle of inclusion-exclusion. Let $A_i$ denote the collection of permutations that fix $i$. Then the collection of $A$ of derangments in $S_n$ is just the complement of

$$A_1\cup A_2\cup \mathrm{\cdots }\cup A_n$$

in $S_n$. Let $C=\{A_1,\mathrm{\dots },A_n\}$ and $I_k$ be the $k$-fold intersection of members of $C$ (that is, each member of $I_k$ has the form $A_{j_1}\cap \mathrm{\cdots }\cap A_{j_k}$). We can interpret a member of $I_k$ as a set of permutations that fix $k$ elements from $\{1,\mathrm{\dots },n\}$. The cardinality of each of these members is $(n-k)!$. Furthermore, there are $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ members in $I_k$. Then,

$d(n)$ $=$ $|A|=|S_n|-|A_1\cup \mathrm{\cdots }\cup A_k\cup \mathrm{\cdots }\cup A_n|$

$=$ $n!-\left[{\displaystyle \sum _{S\in I_1}}|S|-\mathrm{\cdots }+{(-1)}^k{\displaystyle \sum _{S\in I_k}}|S|+\mathrm{\cdots }+{(-1)}^n{\displaystyle \sum _{S\in I_n}}|S|\right]$

$=$ $n!-\left[\left({\displaystyle \genfrac{}{}{0pt}{}{n}{1}}\right)(n-1)!-\mathrm{\cdots }+{(-1)}^k\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)(n-k)!+\mathrm{\cdots }+{(-1)}^n\left({\displaystyle \genfrac{}{}{0pt}{}{n}{n}}\right)(n-n)!\right]$

$=$ $n!-\left[{\displaystyle \frac{n!}{1!}}-\mathrm{\cdots }+{(-1)}^k{\displaystyle \frac{n!}{k!}}+\mathrm{\cdots }+{(-1)}^n{\displaystyle \frac{n!}{n!}}\right]$

$=$ $n!{\displaystyle \sum _{k=0}^n}{\displaystyle \frac{{(-1)}^k}{k!}}$

With this equation, one can easily derive the recurrence relation

$$d(n)=nd(n-1)+{(-1)}^n.$$

Apply this formula twice, we are led to another recurrence relation

$$d(n)=(n-1)\left[d(n-1)+d(n-2)\right].$$

Application. A group of $n$ men arrive at a party and check their hats. Upon departure, the hat-checker, being forgetful, randomly (meaning that the distribution of picking any hat out of all possible hats is a uniform distribution) hands back a hat to each man. What is the probability $p(n)$ that no man receives his own hat? Does this probability go to $0$ as $n$ gets larger and larger?

Answer: According to the above calculation,

$$p(n)=\frac{d(n)}{n!}=\sum _{k=0}^n\frac{{(-1)}^k}{k!}.$$

Therefore,

$$\underset{n\to \mathrm{\infty }}{lim}p(n)=\frac{1}{e}\approx 0.368.$$

Title	derangement
Canonical name	Derangement
Date of creation	2013-03-22 16:05:04
Last modified on	2013-03-22 16:05:04
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	7
Author	CWoo (3771)
Entry type	Definition
Classification	msc 05A15
Classification	msc 05A05
Classification	msc 60C05