Number of permutations that are derangements

there are about n! / e derangements and the probability that a random permutation is a derangement is 1 / e.

This result may also be proved by inclusion-exclusion. Using the sets Ap where \begin{matrix}1\le p\le n\end{matrix} to denote the set of permutations that fix p, we have

\left| \bigcup_p A_p \right| = \sum_p \left| A_p \right| \; - \; \sum_{p<q} \left| A_p \cap A_q \right| \; + \; \sum_{p<q<r} \left| A_p \cap A_q \cap A_r \right| \; - \; \cdots \; \pm \; \left| A_p \cap \; \cdots \; \cap A_s \right|.

This formula counts the number of permutations that have at least one fixed point. The cardinalities are as follows:

\left| A_p \right| = (n-1)!\; , \; \; \left| A_p \cap A_q \right| = (n-2)!\; , \; \; \left| A_p \cap A_q \cap A_r \right| = (n-3)!\; , \; \ldots

Hence the number of permutations with no fixed point is

n! \; \; - \; \; {n \choose 1} (n-1)! \; \; + \; \; {n \choose 2} (n-2)! \; \; - \; \; {n \choose 3} (n-3)! \; \; + \; \; \cdots \; \; \pm \; \; {n \choose n} (n-n)!

or

n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots \pm \frac{1}{n!} \right) = n! \sum_{k=0}^n \frac{(-1)^k}{k!}

and we have the claim.

1 comment:

  1. UnknownNovember 21, 2014 at 5:15 AM

    I would like to use your blog's username. Could you please change your blog's username so that I can use it as your blog seems to be pretty much dead. Thank You very much.

    ReplyDelete

Subscribe to: Post Comments (Atom)

View My Stats

Followers