23.5. Derangements of n Objects

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 kind of arrangement where no object appears in its original position. For example, if we have three objects labeled 1, 2, and 3, a derangement would require that 1 is not in the first place, 2 is not in the second, and 3 is not in the third. This concept is crucial when solving combinatorial problems where we need to re-arrange items in a way that ensures original positions are avoided.

Imagine a situation where you and your friends are inviting each other to sit down for a dinner party. If you have a seating plan where each person has a designated seat but they end up sitting in seats that don't match their original plans, that's similar to a derangement. If each person is to sit somewhere other than their assigned seat, none of them can occupy their expected spot.

We can divide the set of the derangements of n objects into 2 categories. We consider the element which is at the first position.

To understand derangements better, we categorize them based on the element that occupies the first position. For the element placed first, we can either have it occupy another position (say the k-th position) or restrict it from being at that position. Category one allows the first element to also occupy the k-th position, while category two disallows this. This division helps in systematically counting all possible valid derangements.

Think of arranging books on a shelf, where each book has a specific place marked. If the first book (a_1) is placed somewhere else, it can either go back where it shouldn't be (occupying the k-th place, which is flawed) or be placed in any other position except where it's originally intended. Thus, we can approach derangements by considering those two scenarios of placement.

From each category, we can derive how many ways there are to derange the remaining n - 2 or n - 1 elements.

In category one, placing the first item in the first position and the k-th item in the k-th position means we only need to consider deranging the remaining n - 2 items. In category two, since the first item occupies the first position and cannot take the k-th position, we are forced to derange the n - 1 remaining elements. Each scenario gives us a count of possible derangements, which we can sum up to find the total.

Returning to the book example, if the first book is placed in a different spot but ends up not being allowed to go back to its labeled spot (the k-th one), we now have fewer books to rearrange as we continue the exercise. Each successful misplacement of a book means further decisions that can be made based on where not to place each one.

The total number of derangements D(n) can be calculated by taking the cases from both categories for all n elements.

To find the total number of derangements of n objects, we take into account the results from both categories described earlier. By considering how many valid arrangements exist for each scenario where the first element is fixed, we can combine these counts. For n objects, we can express this mathematically as D(n) = (n-1) * (D(n-1) + D(n-2)). This relationship ties the number of derangements directly to those of smaller sets.

Picture a group project where team members must present their parts on a stage, and each slide assigned must be delivered by a different member. By understanding the interactions and placements of who stands on the stage at any one time, we can repeatedly build an increasing tally of successful presentations. This results in a complete picture of how many different valid presentations can be achieved.

--