## You are here

Homederangement

## Primary tabs

# derangement

Let $S_{n}$ be the symmetric group of order $n\geq 1$. A permutation $\phi\in S_{n}$ without a fixed point (that is, $\phi(i)\neq i$ for any $i\in\{1,\ldots,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\cdots\cup A_{n}$ |

in $S_{n}$. Let $C=\{A_{1},\ldots,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\cdots\cap A_{{j_{k}}}$). We can interpret a member of $I_{k}$ as a set of permutations that fix $k$ elements from $\{1,\dots,n\}$. The cardinality of each of these members is $(n-k)!$. Furthermore, there are $n\choose k$ members in $I_{k}$. Then,

$\displaystyle d(n)$ | $\displaystyle=$ | $\displaystyle|A|=|S_{n}|-|A_{1}\cup\cdots\cup A_{k}\cup\cdots\cup A_{n}|$ | ||

$\displaystyle=$ | $\displaystyle n!-\Big[\sum_{{S\in I_{1}}}|S|-\cdots+(-1)^{k}\sum_{{S\in I_{k}}% }|S|+\cdots+(-1)^{n}\sum_{{S\in I_{n}}}|S|\Big]$ | |||

$\displaystyle=$ | $\displaystyle n!-\Big[{n\choose 1}(n-1)!-\cdots+(-1)^{k}{n\choose k}(n-k)!+% \cdots+(-1)^{n}{n\choose n}(n-n)!\Big]$ | |||

$\displaystyle=$ | $\displaystyle n!-\Big[\frac{n!}{1!}-\cdots+(-1)^{k}\frac{n!}{k!}+\cdots+(-1)^{% n}\frac{n!}{n!}\Big]$ | |||

$\displaystyle=$ | $\displaystyle n!\sum_{{k=0}}^{{n}}\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)\big[d(n-1)+d(n-2)\big].$ |

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,

$\lim_{{n\to\infty}}p(n)=\frac{1}{e}\approx 0.368.$ |

## Mathematics Subject Classification

05A15*no label found*05A05

*no label found*60C05

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections