We use the Inclusion-Exclusion Principle to enumerate relative derangements.

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,

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

It turns out that the relative derangement numbers, are related to the derangement numbers .

We now turn to relative derangements in a circular setting.

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