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

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

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

- Proof
- Note that since can be written using binomial coefficients as Replacing by in the formula for , we have Now we add and use Pascal’s identity to combine the summands