We use the Inclusion-Exclusion Principle to enumerate derangements.
Derangements A derangement is a permutation in which each of the permuted
objects is forbidden from exactly one distinct position. The number of derangements
of a set of elements is denoted by .
In its simplest form, a derangement of the set is a permutation of in which
the is not in the first position, the is not in the second position and so
on.
How many derangements are there of the word ?
In this case, a derangement consists of a permutation of the letters in the word in which the is not in the first position, the is not in the second position and the is not in the third position. The list of such permutations is short enough (certainly less than ) that the count can be obtained by listing its members. They are Hence, there are derangements of the letters in the word and we conclude that .
In this case, a derangement consists of a permutation of the letters in the word in which the is not in the first position, the is not in the second position and the is not in the third position. The list of such permutations is short enough (certainly less than ) that the count can be obtained by listing its members. They are Hence, there are derangements of the letters in the word and we conclude that .
We now use the Inclusion-Exclusion Principle to count the number of derangements of the set in which the number is not in the position for each from to .
Derangements The number of derangements of the set in which the number is not
in the position for is given by
- Proof
- For each from to , let be the set of permutations of that has in the
position. Then and for each . Furthermore, and . We see that the number of
elements in the intersection of of these sets will be .
We seek . By De Morgan’s Law (for sets), the Rule for Complements and the Inclusion-Exclusion Principle, we have \begin{align*} D_n &= |A_1^c \cap A_2^c \cap \cdots \cap A_n^c| = |\left (A_1 \cup A_2 \cup \cdots \cup A_n\right )^c| = |S| - |A_1 \cup A_2 \cup \cdots \cup A_n|\\ &= n! - \bigg [\sum _{i =1}^n |A_i| - \sum _{1 =i<j}^n |A_i\cap A_j|+ \sum _{1 =i<j< k}^n |A_i\cap A_j \cap A_k| \\ &\hspace{2.5 in} - \cdots + (-1)^{n-1} |A_1 \cap A_2 \cap \cdots \cap A_n|\bigg ]\\ &= n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \binom{n}{3}(n-3)! + \cdots + (-1)^n \binom{n}{n}(n-n)!\\ &= n! - n! + \frac{n!}{2!} - \frac{n!}{3!} + \cdots + (-1)^n \frac{n!}{n!}\\ &= n! \cdot \sum _{k=0}^n (-1)^k \frac{1}{k!} \end{align*}
Recall the Maclaurin series expansion for the exponential function: Letting gives
Thus, we see in the truncation of this series for at the term.
example 2 Compute .
\begin{align*} D_8 &= 8! \sum _{k=0}^8 \frac{(-1)^k}{k!}\\ &= 8!\bigg (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}- \frac{1}{5!} + \frac{1}{6!} - \frac{1}{7!} + \frac{1}{8!}\bigg ) \\ &= \frac{8!}{2!} - \frac{8!}{3!} + \frac{8!}{4!} - \frac{8!}{5!} + \frac{8!}{6!} - \frac{8!}{7!} + \frac{8!}{8!} \\ &= 14833 \end{align*}
\begin{align*} D_8 &= 8! \sum _{k=0}^8 \frac{(-1)^k}{k!}\\ &= 8!\bigg (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}- \frac{1}{5!} + \frac{1}{6!} - \frac{1}{7!} + \frac{1}{8!}\bigg ) \\ &= \frac{8!}{2!} - \frac{8!}{3!} + \frac{8!}{4!} - \frac{8!}{5!} + \frac{8!}{6!} - \frac{8!}{7!} + \frac{8!}{8!} \\ &= 14833 \end{align*}
It is also possible to use combinatorial reasoning to obtain a recursive formula for derangement numbers, .
- Proof
- Let and consider the derangements of where the is in the first position.
These derangements can be partitioned into two sets- those permutations for
which is in the position and those for which is not in the position.
Case 1) is in the first position and is in the position. The number of such derangements is simply since the remaining elements can be permuted among themselves in ways in order to obtain a derangement.
Case 2) is in the first position and is not in the position. The number of derangements in this case is the number of derangements of the string: , which is . The result follows by noting that there are possibilities for the choice of .
example 3 Use the values and and the recursive formula for to compute and
.
We have \begin{align*} D_2 &= (2-1)(D_0 + D_1) = 1\\ D_3 &= (3-1)(D_1 + D_2) = 2(0+1) = 2\\ D_4 &= (4-1)(D_2 + D_3) = 3(1+2) = 9\\ D_5 &= (5-1)(D_4 + D_5) = 4(2+9) = 44\\ \end{align*}
We have \begin{align*} D_2 &= (2-1)(D_0 + D_1) = 1\\ D_3 &= (3-1)(D_1 + D_2) = 2(0+1) = 2\\ D_4 &= (4-1)(D_2 + D_3) = 3(1+2) = 9\\ D_5 &= (5-1)(D_4 + D_5) = 4(2+9) = 44\\ \end{align*}
example 4 (The hat check problem)
Suppose that people check their hats at an establishment and that, at closing time, the hats are returned at random to the people. What is the probability that no one receives their own hat?
The total number of ways to return the hats to the people is and since each of these permutations is equally likely as the hats at returned at random, the probability of any particular permutation of the returned hats is . The probability that no one receives their own hat is thus since there are ways to return the hats so that no one receives their own hat.
Suppose that people check their hats at an establishment and that, at closing time, the hats are returned at random to the people. What is the probability that no one receives their own hat?
The total number of ways to return the hats to the people is and since each of these permutations is equally likely as the hats at returned at random, the probability of any particular permutation of the returned hats is . The probability that no one receives their own hat is thus since there are ways to return the hats so that no one receives their own hat.
(problem 5) Seven people check their hats at an establishment. In how many ways
can the hats be returned so that
a) no person receives their own hat?
b) at least one person receives their own hat?
c) at least two people receive their own hat?
d) exactly six people receive their own hat?
a) no person receives their own hat?
b) at least one person receives their own hat?
c) at least two people receive their own hat?
d) exactly six people receive their own hat?
There is a second, slightly simpler recursion formula for the derangement numbers that can be derived from the recursion formula in the proposition above.
(problem 6) Verify that the recursion relation holds for and . Then, use
mathematical induction to prove that it holds for all .
(problem 7) Use the recursion relation in problem 6 and your result for from problem
3 to compute and .
Permutations can be partitioned into the number of objects which are not moved from their original position.
2025-03-06 01:12:31