Derangements and the Principle of Inclusion-Exclusion

Hello! It's great to see you again. In our previous lesson, we saw how the Principle of Inclusion-Exclusion (PIE) can be combined with the stars and bars method to solve complex distribution problems involving upper limits. The core strategy was to count the total possibilities and then subtract the "bad" cases—those that violated our constraints.

Today, we'll apply this exact same strategic thinking to a completely different, and very famous, problem in combinatorics: counting permutations. Our goal is to use PIE to determine the number of derangements, which are permutations where no element ends up in its original position. This is a classic application of PIE and a cornerstone of enumerative combinatorics, frequently appearing in Olympiad-style problems.

What is a Derangement?

Imagine a hat-check attendant who has collected hats from $n$ guests. At the end of the night, the attendant hands back the hats randomly. A derangement occurs if no single guest receives their own hat back.

Formally, a derangement of a set of $n$ elements is a permutation of those elements such that no element appears in its original position. The number of derangements of $n$ elements is often denoted as $D_{n}$ or $! n$ .

Let's look at a small example with $n = 4$ elements, say ${1, 2, 3, 4}$ . There are $4! = 24$ total ways to arrange these elements.

This image displays all 24 permutations of four items. The permutations inside the red boxes are derangements—notice that in each of these, no number is in its original position (e.g., in `2 1 4 3`, `1` is not in the first spot, `2` is not in the second, etc.). There are 9 such derangements for n=4.

To see how we can count these without listing them all, we'll turn to the Principle of Inclusion-Exclusion.

Setting up the PIE Framework

Our goal is to count permutations where no element is in its original place. This "no" condition is a strong clue that PIE will be useful. As we did in the last lesson, we will count the total number of permutations and subtract the "bad" ones.

The universe ( $U$ ) is the set of all possible permutations. For $n$ elements, $∣ U ∣ = n!$ .
A permutation is "bad" if at least one element is in its original position (i.e., it is not a derangement).
Let's define a property $P_{i}$ to mean that element $i$ is in its original position. Let $A_{i}$ be the set of all permutations that have property $P_{i}$ .

The set of all "bad" permutations is the union $A_{1} \cup A_{2} \cup \dots \cup A_{n}$ . The number of derangements, $D_{n}$ , is the number of permutations with none of these properties. Therefore:
$D_{n} = n! - ∣ A_{1} \cup A_{2} \cup \dots \cup A_{n} ∣$
Now, our task is to calculate the size of that union using PIE.

Applying PIE to Count Derangements

The video below provides a clear, step-by-step walkthrough of how to use PIE to count derangements. It first demonstrates the method for $n = 4$ and then generalizes the result.

[Discrete Mathematics] Derangements

This video from TrevTutor, titled "Derangements", gives a fantastic explanation of how to derive the derangement formula using PIE.

First, watch the calculation for n=4 from this section. The logic directly mirrors what we're about to discuss. Next, watch the derivation of the general formula from this segment. This is the core of today's lesson. Pay close attention to how the binomial coefficient terms from PIE simplify.

Let's formalize the steps shown in the video. The PIE formula for the size of the union is:
$∣ A_{1} \cup \dots \cup A_{n} ∣ = \sum ∣ A_{i} ∣ - \sum ∣ A_{i} \cap A_{j} ∣ + \sum ∣ A_{i} \cap A_{j} \cap A_{k} ∣ - \dots$

First term: $\sum ∣ A_{i} ∣$
This represents the sum of the sizes of sets where at least one element is fixed.
- How many permutations fix element $i$ ? If we fix element $i$ , we are free to permute the remaining $n - 1$ elements in $(n - 1)!$ ways. So, $∣ A_{i} ∣ = (n - 1)!$ .
- There are $(1 n)$ ways to choose which single element to fix.
- Thus, the first term is $(1 n) (n - 1)!$ .
Second term: $\sum ∣ A_{i} \cap A_{j} ∣$
This represents permutations where at least two elements are fixed.
- How many permutations fix elements $i$ and $j$ ? We fix those two and permute the remaining $n - 2$ elements in $(n - 2)!$ ways. So, $∣ A_{i} \cap A_{j} ∣ = (n - 2)!$ .
- There are $(2 n)$ ways to choose which pair of elements to fix.
- The second term is $(2 n) (n - 2)!$ .
General term for $k$ fixed elements:
The size of the intersection of $k$ such sets is $(n - k)!$ . There are $(k n)$ ways to choose the $k$ elements to fix. So, the $k$ -th term in the PIE sum is $(k n) (n - k)!$ .

This logic is explained in the following resource, which presents the derivation from a textual perspective.

The Inclusion-Exclusion Principle

This document provides a concise mathematical derivation of the formula for D(n).

Read the section titled Now back to (3). It clearly lays out how to compute the size of the intersections and assembles the full PIE formula to find the number of non-derangements.

The General Formula and a Surprising Connection

As the resources show, when we assemble the PIE formula, a beautiful simplification occurs. The $k$ -th term of the sum for non-derangements is:
$(k n) (n - k)! = \frac{n !}{k ! ( n - k )!} (n - k)! = \frac{n !}{k !}$
So, the number of non-derangements is:
$∣ A_{1} \cup \dots \cup A_{n} ∣ = \sum_{k = 1}^{n} (- 1)^{k - 1} (k n) (n - k)! = \sum_{k = 1}^{n} (- 1)^{k - 1} \frac{n !}{k !}$
The number of derangements $D_{n}$ is $n! - ∣ A_{1} \cup \dots \cup A_{n} ∣$ :
$D_{n} = n! - (\frac{n !}{1 !} - \frac{n !}{2 !} + \frac{n !}{3 !} - \dots + (- 1)^{n - 1} \frac{n !}{n !})$
$D_{n} = n! - \frac{n !}{1 !} + \frac{n !}{2 !} - \frac{n !}{3 !} + \dots + (- 1)^{n} \frac{n !}{n !}$
Factoring out $n!$ gives us the standard formula for derangements:
$D_{n} = n! (1 - \frac{1}{1 !} + \frac{1}{2 !} - \frac{1}{3 !} + \dots + (- 1)^{n} \frac{1}{n !}) = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}$

This sum is the first $n + 1$ terms of the Taylor series for $e^{x}$ evaluated at $x = - 1$ . Recall that:
$e^{- 1} = \frac{1}{e} = \sum_{k = 0}^{\infty} \frac{( - 1 ) ^{k}}{k !} = 1 - \frac{1}{1 !} + \frac{1}{2 !} - \frac{1}{3 !} + \dots$
For even moderately large $n$ , the sum in our $D_{n}$ formula is extremely close to $1/ e$ . This gives us a fantastic approximation:
$D_{n} \approx \frac{n !}{e}$
In fact, $D_{n}$ is the closest integer to $n! / e$ for $n \geq 1$ . This means the probability that a randomly chosen permutation is a derangement, $D_{n} / n!$ , quickly converges to $1/ e \approx 0.367879$ . It's quite remarkable that for any large group of people, the chance that no one gets their own hat back is about 36.8%!

Practice Problems

To master this concept, you must be able to apply it not just to find $D_{n}$ , but also to related problems, like counting permutations with a specific number of fixed points.

The Hat-Check Problem: Five gentlemen attend a party and leave their hats at the door. At the end, they hastily grab hats on their way out. In how many ways could it happen so that none of the gentlemen leaves with his own hat? (This is Example 1.6.5 from the "Advanced Counting Using PIE" text).
Partially Correct Permutations: How many permutations of the set ${1, 2, 3, 4, 5, 6}$ fix exactly 2 elements?
The Grinch's Mischief: The Grinch sneaks into a room with 7 presents for 7 different people and switches the name labels. (This is based on Exercise 10 in the same text).
a. In how many ways can he do this so that no present ends up with its original label?
b. In how many ways can he do this so that exactly 3 presents keep their original labels?
c. In how many ways can he do this so that exactly 6 presents keep their original labels?
A Sneaky Derangement: Let $S = {1, 2, 3, 4, 5, 6, 7}$ . How many injective functions $f : S \to S$ have the property that for every $x \in S$ , $f (x) \neq = x$ ?

Hint for Problem 2: This is a two-step problem. First, choose which elements will be fixed. Then, figure out what must happen to the remaining elements and count the ways.

Conclusion

Today, we've added a powerful and elegant tool to our combinatorial arsenal. By applying the Principle of Inclusion-Exclusion, we moved from a brute-force listing of permutations to a general and efficient formula for counting derangements.

Key Takeaways:

A derangement is a permutation where no element is in its original position.
We use PIE to count derangements by defining the "bad" properties as elements that are in their original positions (fixed points).
The number of derangements of $n$ elements is given by the formula $D_{n} = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !}$ .
For $n \geq 1$ , $D_{n}$ is the closest integer to $n! / e$ , meaning the probability of a random permutation being a derangement is approximately $1/ e$ .
Many problems can be solved by combining derangements with other counting principles, such as choosing a subset of elements to be fixed and deranging the rest.

In our next lesson, we will continue our exploration of PIE's applications. We will tackle another classic counting problem: finding the number of surjective (or "onto") functions between two finite sets. You will see that the underlying strategy remains the same: identify the total, define the "bad" properties, and use PIE to subtract what you don't want.

Recommended resources