# 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.$
Title derangement Derangement 2013-03-22 16:05:04 2013-03-22 16:05:04 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 05A15 msc 05A05 msc 60C05