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