A permutation of {1,2,…,n} is called a derangement if no element appears in its original position. For example, (2,1,3) is not a derangement of {1,2,3} because 3 is in its original position, but (2,3,1) is a derangement.
Let Dn denote the number of derangements of {1,2,…,n}.
- Using the Inclusion-Exclusion Principle, derive a closed-form formula for Dn.
- what is the probability that a uniformly random permutation of {1,2,…,n} is a derangement ?