Derangements
A derangement is a permutation with no fixed points. A random permutation of is a derangement with probability
which tends to as .
Example 2.7 (Counting Derangements)
A derangement is a permutation with no fixed points. Let
Pick a permutation at random. Consider the probability that it is in . For , let
Then
So
Using Inclusion-Exclusion Formula 2.4, we have
Therefore,
Note that as , .
Related
Stated in
- Example 2.7 (Counting Derangements)§2.2 Inclusion-Exclusion Formula