We use the Inclusion-Exclusion Principle to enumerate relative derangements.
Relative Derangements A relative derangement of a permutation of objects is
another permutation of these objects for which each object in the original
permutation has a different successor. The number of relative derangements of a
permutation consisting of objects is denoted by .
In its simplest form, a relative derangement of the permutation is a permutation of
which does not contain any of the strings .
List the relative derangements of the letters .
We consider permutations of for which the does not proceed the , and the does not proceed the . The relative derangements of are Since there are 3 of them, we can write . Note that while is a derangement of , it is not a relative derangement since follows in both and .
We consider permutations of for which the does not proceed the , and the does not proceed the . The relative derangements of are Since there are 3 of them, we can write . Note that while is a derangement of , it is not a relative derangement since follows in both and .
Before we find a general formula for , we will explore . We wish to count the number
of relative derangements of .
Let be the permutations of which contain the string ;
let be the permutations of which contain the string ;
let be the permutations of which contain the string ;
and let be the permutations of which contain the string .
The number of permutations in is then number of permutations of the symbols .
Since there are 4 distinct symbols, we have = 4!. Furthermore, as well. Next we
consider and . Permutations in the set include the strings and and hence they
contain the string . Thus, since they consist of permutations of the symbols . Now
consider permutations in the set . These permutations contain the strings and .
Unlike the previous situation, these strings do not overlap. We have anyway, since
we are considering permutations of the three symbols . We see that whether the
strings overlap or not, the number of permutations containing the same number of
2-strings is the same. In a similar manner, when we consider three way intersections
we obtain the same number of permutations even though on the surface they
appear to be different. Consider and . In the first case, the set contains
permutations of the symbols and in the second case . In either case there are
permutations, so . In this way, we see that the three way intersections all contain the
same number of permutations. We are now able to compute . We have \begin{align*} Q_5 &= |A_1^c \cap A_2^c \cap A_3^c \cap A_4^c|\\ &= |(A_1 \cup A_2 \cup A_3 \cup A_4)^c|\\ &= |S| - |A_1 \cup A_2 \cup A_3 \cup A_4|\\ &= |S| - \sum _{i =1}^4 |A_i| + \sum _{1=i<j}^4 |A_i \cap A_j|\\ & \qquad - \sum _{1 = i <j<k}^4 |A_i \cap A_j \cap A_k| \;\;+\;\; |A_1 \cap A_2 \cap A_3 \cap A_4|\\ &= 5! - \binom{4}{1}4! + \binom{4}{2} 3! - \binom{4}{3}2! + 1\\ &= 120 - 96 + 36 - 8 +1 = 53 \end{align*}
We now compute the number of relative derangements,
Relative Derangements The number of relative derangements of , i.e., the number of
permutations of the set which do not contain any of the strings , is given by
- Proof
- For each from to , let be the set of permutations of that contain the
string Then and for each . Furthermore, based on the pattern we observed when
computing , and and in general, the number of elements in the intersection of of
these sets will be .
We are now ready to compute By De Morgan’s Law (for sets), the Rule for Complements and the Inclusion-Exclusion Principle, we have \begin{align*} Q_n &= |A_1^c \cap A_2^c \cap \cdots \cap A_{n-1}^c| = |\left (A_1 \cup A_2 \cup \cdots \cup A_{n-1}\right )^c| = |S| - |A_1 \cup A_2 \cup \cdots \cup A_{n-1}|\\ &= n! - \bigg [\sum _{i =1}^{n-1} |A_i| - \sum _{1 =i<j}^{n-1} |A_i\cap A_j|+ \sum _{1 =i<j< k}^{n-1} |A_i\cap A_j \cap A_k| \\ &\hspace{2.5 in} - \cdots + (-1)^{n-2} |A_1 \cap A_2 \cap \cdots \cap A_{n-1}|\bigg ]\\ &= n! - \binom{n-1}{1}(n-1)! + \binom{n-1}{2}(n-2)! - \binom{n-1}{3}(n-3)! + \cdots + (-1)^{n-1} \binom{n-1}{n-1}(1)!\\ &= (n-1)!\left [n -\frac{n-1}{1!} + \frac{n-2}{2!} - \frac{n-3}{3!} + \cdots + (-1)^{n-1} \frac{1}{(n-1)!}\right ]\\ &= (n-1)! \cdot \sum _{k=0}^{n-1} (-1)^k \frac{n-k}{k!} \end{align*}
(problem 2) A herd of 30 elephants is walking single file on a long trek. At the
midpoint, they stop at a watering hole. Upon resuming their single file march, they
decide that no elephant should have the same elephant immediately in front of
them. In how many single file formations can the elephants resume their
journey?
(problem 3) Use the Inclusion-Exclusion Principle to compute the number of relative
derangements of ABCDE.
It turns out that the relative derangement numbers, are related to the derangement numbers .
We now turn to relative derangements in a circular setting.
(problem 5a) Alice, Bob, Charles and Diane sit at a round table (in that order) for
lunch every weekday. One day, Bob suggests that they change seats in such a way
that no one is sitting to the left of the usual person.
i) Determine the number of possible new seating arrangements by explicitly listing them.
ii) Determine the number of new seating arrangements using the Inclusion-Exclusion Principle.
i) Determine the number of possible new seating arrangements by explicitly listing them.
ii) Determine the number of new seating arrangements using the Inclusion-Exclusion Principle.
(problem 5b) Alice, Bob, Charles, Diane and Ethel sit at a round table (in that order)
for lunch every weekday. One day, Bob suggests that they change seats in such as way
that no one is sitting to the left of the usual person.
i) Determine the number of possible new seating arrangements by explicitly listing them.
ii) Determine the number of new seating arrangements using the Inclusion-Exclusion Principle.
i) Determine the number of possible new seating arrangements by explicitly listing them.
ii) Determine the number of new seating arrangements using the Inclusion-Exclusion Principle.
- Proof
- Let be the set of all circular permutations of . Let be the set of circular permutations containing the string for and let be the set containing the string . We seek . We have \begin{align*} \left |\bigcap _{i=1}^n A_i^c\right | &= |S| - \left |\bigcup _{i=1}^n A_i\right |\\ &= (n-1)! - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + \cdots + (-1)^n \left |\bigcap _{i=1}^n A_i\right |\\ &= (n-1)! - \binom{n}{1} (n-2)! + \binom{n}{2} (n-3)! - \binom{n}{3} (n-4)! + \cdots \\ & \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad + (-1)^{n-1} \binom{n}{n-1} (n-n)! \;+ (-1)^n\\ &= \sum _{k=0}^{n-1} (-1)^k \binom{n}{k} (n-k-1)! \;+ (-1)^n\\ &= \sum _{k=0}^{n-1} (-1)^k \frac{n!}{k!(n-k)!} (n-k-1)! \;+ (-1)^n\\ &= n! \sum _{k=0}^{n-1} (-1)^k \frac{1}{(n-k) k!} \;+ (-1)^n \end{align*}
- Proof
- Note that since can be written using binomial coefficients as Replacing
by in the formula for , we have \begin{align*} C_{n+1} &= \sum _{k=0}^{n} (-1)^k\binom{n+1}{k}(n-k)! + (-1)^{n+1}\\ &= n! + \sum _{k=1}^{n} (-1)^k \binom{n+1}{k} (n-k)! + (-1)^{n+1}\\ &= n! + \sum _{k=0}^{n-1} (-1)^{k+1} \binom{n+1}{k+1} (n-k-1)! + (-1)^{n+1} \end{align*}
Now we add and use Pascal’s identity to combine the summands \begin{align*} C_n + C_{n+1} &= \sum _{k=0}^{n-1} (-1)^{k} \binom{n}{k} (n-k-1)! + (-1)^{n} + n! + \sum _{k=0}^{n-1} (-1)^{k+1} \binom{n+1}{k+1} (n-k-1)! + (-1)^{n+1}\\ &= n! + \sum _{k=0}^{n-1} (-1)^k \left [\binom{n}{k} - \binom{n+1}{k+1}\right ] (n-k-1)!\\ &= n! + \sum _{k=0}^{n-1} (-1)^k \left [ - \binom{n}{k+1}\right ] (n-k-1)!\\ & = n! - \sum _{k=0}^{n-1} (-1)^k \binom{n}{k+1} (n-k-1)!\\ &= n! - \sum _{k=1}^{n} (-1)^{k-1} \binom{n}{k} (n-k)!\\ &= n! + \sum _{k=1}^{n} (-1)^k \binom{n}{k} (n-k)!\\ &= n! + n! \sum _{k=1}^{n} (-1)^k \frac{1}{k!}\\ & = n! \sum _{k=0}^{n} (-1)^k \frac{1}{k!}\\ &= D_n \end{align*}