We use the Inclusion-Exclusion Principle to enumerate derangements.

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 .

- 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*}

\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 ways to permute , (the 1 is in the position) such that 2 is not first, 3 is not second, ..., is not , ..., and the is not last. This is the number of derangements of the symbols and hence it is .

The result follows by noting that there are possibilities for the choice of .

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*}

people check their hats at an establishment. 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 in this manner.

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.

Permutations can be partitioned into the number of objects which are not moved from their original position.

2024-09-27 14:04:21