# 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 |