23.5.1. Categories of Derangements

A derangement of n objects is a permutation of those n objects such that none of the objects is at its correct position.

A derangement is a specific type of arrangement (or permutation) of objects where no object appears in its original position. For example, if we have three objects labeled 1, 2, and 3, a derangement would be an arrangement like (2, 3, 1) or (3, 1, 2), where no object retains its original index (1 is not in position 1, 2 is not in position 2, and so forth).

Imagine you and two friends each have a unique hat, and you want to swap the hats such that no one wears their own hat. If everyone swaps their hats in a way that ends up with each person wearing a different friend's hat (like you wearing your friend's hat #3 and so on), that's a derangement.

We can divide the set of the derangements of n objects into 2 categories based on the element in the first position.

The concept of categorizing derangements begins by fixing an item (let's call it 'a') in the first position. There are two scenarios to consider for the position of this item in a valid derangement. In the first category, the item 'a' can be placed in another position (let's say position 'k'). In this case, you will have disturbed the original arrangement of 'a' and will focus on deranging the remaining objects. In the second category, you avoid placing 'a' in position 'k'. This means you're further restricted as 'a' cannot occupy its original position or leave its assigned place, focusing now on the derangement of the rest of the items.

Thinking of a class where students are rearranging their seats, let’s fix John in the front row. In the first category, John moves to a different seat in the same row, causing his previous seat to be filled by someone else, which changes how everyone else rearranges. In the second category, if John moves to another row entirely, he has still disrupted another person's seat arrangement while ensuring he doesn't end up where he started.

Category one: where element 'a' is occurring at the kth position; category two: where element 'a' is not allowed to occur at the kth position.

In category one, placing 'a' in the kth position allows you to once again derange the remaining elements filling in the gaps. Thus, you can derive a number of derangements from the arrangements that only include the remaining n-2 elements. In category two, if 'a' cannot occupy the kth spot, the problem simplifies to deranging n-1 elements since 'a' now has other constraints on its movement. Effectively, both categories lead to manageable subproblems that can be solved systematically.

Returning to our classroom analogy: if John can sit in another chair (the kth position), we're left with a bunch of seats available to rearrange others into new positions (which is category one). But if we've decided John cannot sit anywhere near his original desk (the kth position), then he has to choose from other options, leaving us to rethink the rest of the seating, narrowing our focus to a constrained arrangement of n-1 students.

--