22.2.4. Derangements

So, what exactly is a derangement? Imagine you have 3 persons, person 1 (P1), person 2 (P2), and person 3 (P3), and they have their respective caps, cap 1 (C1), cap 2 (C2), and cap 3 (C3). Now the derangement of caps is an arrangement of the 3 caps, so that no cap goes back to its original owner.

Derangements are specific kinds of permutations where no element appears in its original position. For example, if we have three people with three caps, a derangement is an arrangement where no one has their own cap. If P1 initially has C1, after the derangement, P1 cannot have C1. Instead, they could have either C2 or C3, while ensuring the other persons also do not have their own caps.

Think of a game where three friends are supposed to pick a random gift from a set of three gifts, but each gift is marked with the name of the owner of the gift. A derangement means that no friend picks their own gift. They can exchange gifts in such a way that everyone ends up with someone else's gift entirely instead.

The number of derangements of n objects is denoted by this quantity D_n. D_0 is 1 because if there are no objects, there is one way to do nothing. D_1 is 0 because if there is only one object, it cannot be deranged. D_2 is 1 likewise.

The notations D_n refer to the number of derangements for n objects. As noted, D_0 (no objects) has one arrangement, which is doing nothing. However, for one object, there’s no way to place it where it doesn’t end up in the original position, thus D_1 is 0. For two objects, the only way to swap them is to exchange their places, providing one derangement.

Imagine you have a test with one question where you must choose between two answers. If there’s only one question, choosing wrongly still means you picked the only available choice, which is predefined. In terms of derangements, it conceptualizes how impossible it is to have an arrangement with just one choice that fits the rules.

To find out the number of derangements, we will use the alternate form of inclusion-exclusion. The property P_i is that you do not want the ith element to be at the position i. As per the definition, if I take the union of the sets S to S, it gives me all the permutations where at least one of the elements is still at its original position.

Using the principle of inclusion-exclusion, we want to exclude the cases where any of the elements are still in their original positions. This is done by considering the sets where an element remains fixed (i.e., S_i for element i at its position). The formula considers the count of all permutations and subtracts the cases where this rule is violated. By applying the combination rules, we can interpolate the arrangements effectively and determine D_n.

Think about organizing a class of students for a play where each student has a specific part. If one student stays in their role, they disrupt the flow of the play, similar to a derangement where each role needs to be filled by someone new. We need to find a way to switch roles only so that no original actor maintains their spot, achieving an effective performance without duplicates.

--