derangement
Let be the symmetric group of order . A permutation without a fixed point
(that is, for any ) is called a derangement
.
In combinatorial theory, one is usually interested in the number of derangements in . It is clear that , and . It is also not difficult to calculate for small . For general , one can appeal to the principle of inclusion-exclusion. Let denote the collection of permutations that fix . Then the collection of of derangments in is just the complement of
in . Let and be the -fold intersection of members of (that is, each member of has the form ). We can interpret a member of as a set of permutations that fix elements from . The cardinality of each of these members is . Furthermore, there are members in . Then,
With this equation, one can easily derive the recurrence relation
Apply this formula twice, we are led to another recurrence relation
Application. A group of 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 that no man receives his own hat? Does this probability go to as gets larger and larger?
Answer: According to the above calculation,
Therefore,