Derangements

Pillar: Fix — "Fix which elements are NOT fixed points (which slots we're excluding). Count the rest." Pillar: Set — "Apply IE: subtract sets \(A_i\) = 'element \(i\) is fixed,' add back intersections."

---

The Setup

Five friends each bring a gift to a Secret Santa party. The gifts are shuffled and handed back at random. What's the probability that nobody gets their own gift?

Label the friends \(1\) through \(5\). A distribution of gifts is just a permutation \(\sigma\) of \(\{1, 2, 3, 4, 5\}\), where friend \(i\) receives gift \(\sigma(i)\). Friend \(i\) gets their own gift when \(\sigma(i) = i\) — that's a fixed point. You want permutations with zero fixed points.

For \(n = 5\), there are \(5! = 120\) permutations total. How many have no fixed points? Brute force is fine for \(n = 5\), but what about \(n = 200000\)? You need a formula, and inclusion-exclusion hands you one.

---

The Key Idea

The direct count — "all permutations where nobody is fixed" — is hard because the constraints interact. Person 1 not being fixed affects where person 1's gift goes, which affects everyone else.

Flip the question. Instead of counting what you want directly, count what you want to exclude and subtract. Define \(A_i\) = "the set of permutations where person \(i\) IS a fixed point." You want permutations in NONE of the \(A_i\)'s. That's the complement of the union \(A_1 \cup A_2 \cup \cdots \cup A_n\).

Through the Fix pillar: fix which people are stuck at their own position, then count the rest freely. Through the Set pillar: use IE to combine the contributions of each subset of "fixed" people, alternating between adding and subtracting.

---

Definition

A derangement of \(\{1, 2, \ldots, n\}\) is a permutation \(\sigma\) such that \(\sigma(i) \neq i\) for every \(i\). The number of derangements of \(n\) elements is denoted \(D(n)\) (sometimes written \(!n\) or \(D_n\)).

---

Small Cases

Build intuition before the formula.

\(n = 1\): The only permutation is \((1)\), which has \(\sigma(1) = 1\). That's a fixed point. \(D(1) = 0\).

\(n = 2\): Permutations are \((1, 2)\) and \((2, 1)\). Only \((2, 1)\) has no fixed points. \(D(2) = 1\).

\(n = 3\): Permutations of \(\{1, 2, 3\}\):

Permutation	Fixed points	Derangement?
\((1, 2, 3)\)	\(\{1, 2, 3\}\)	No
\((1, 3, 2)\)	\(\{1\}\)	No
\((2, 1, 3)\)	\(\{3\}\)	No
\((2, 3, 1)\)	\(\emptyset\)	Yes
\((3, 1, 2)\)	\(\emptyset\)	Yes
\((3, 2, 1)\)	\(\{2\}\)	No

\(D(3) = 2\). The two derangements are \((2, 3, 1)\) and \((3, 1, 2)\) — both cyclic shifts.

\(n = 4\): \(D(4) = 9\). You can verify by listing all \(24\) permutations, but the formula we're about to derive gives \(24 - 24 + 12 - 4 + 1 = 9\).

---

The IE Derivation

This is the core of the lesson. Every step follows directly from inclusion-exclusion.

Step 1: Define the sets

Let \(A_i\) be the set of permutations of \(\{1, 2, \ldots, n\}\) where element \(i\) is a fixed point (i.e., \(\sigma(i) = i\)).

You want \(D(n) = n! - |A_1 \cup A_2 \cup \cdots \cup A_n|\).

Step 2: Compute \(|A_i|\)

If \(\sigma(i) = i\) is forced, the remaining \(n - 1\) elements can be permuted freely.

\[|A_i| = (n-1)!\]

There are \(\binom{n}{1}\) such sets, and they all have the same size.

Step 3: Compute \(|A_i \cap A_j|\)

If both \(\sigma(i) = i\) and \(\sigma(j) = j\) are forced, the remaining \(n - 2\) elements can be permuted freely.

\[|A_i \cap A_j| = (n-2)!\]

There are \(\binom{n}{2}\) such pairwise intersections.

Step 4: Generalize

For any subset \(S \subseteq \{1, 2, \ldots, n\}\) with \(|S| = k\), forcing all elements in \(S\) to be fixed points leaves \(n - k\) elements free:

\[\left|\bigcap_{i \in S} A_i\right| = (n - k)!\]

There are \(\binom{n}{k}\) subsets of size \(k\), and every such subset gives the same intersection size.

Step 5: Apply IE

\[|A_1 \cup \cdots \cup A_n| = \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} (n-k)!\]

Therefore:

\[D(n) = n! - \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k}(n-k)!\]

Step 6: Simplify

Pull the formula together by starting the sum at \(k = 0\) (the \(k = 0\) term is \(\binom{n}{0} \cdot n! = n!\), which is exactly the \(n!\) out front):

\[D(n) = \sum_{k=0}^{n} (-1)^k \binom{n}{k}(n-k)!\]

Expand \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\):

\[D(n) = \sum_{k=0}^{n} (-1)^k \frac{n!}{k!(n-k)!} \cdot (n-k)! = \sum_{k=0}^{n} (-1)^k \frac{n!}{k!}\]

Factor out \(n!\):

\[\boxed{D(n) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}}\]

Step 7: Verify with \(n = 4\)

\[D(4) = 4! \left(\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}\right) = 24\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right)\]

Compute inside the parentheses: \(0 + 0.5 - 0.1\overline{6} + 0.041\overline{6} = 0.375\).

\[D(4) = 24 \times 0.375 = 9\]

Matches the known value.

---

The Recurrence

There's a second way to compute \(D(n)\) that doesn't need the IE formula at all.

\[D(n) = (n-1)\bigl(D(n-1) + D(n-2)\bigr)\]

with \(D(0) = 1\) (the empty permutation is vacuously a derangement) and \(D(1) = 0\).

Derivation. Consider where element \(n\) goes. It must go to some slot \(j \neq n\) — there are \(n - 1\) choices for \(j\). Now ask: where does element \(j\) go?

• Case 1: \(j\) goes to slot \(n\). Elements \(n\) and \(j\) swap. The remaining \(n - 2\) elements must form a derangement among themselves. That's \(D(n-2)\) ways.

• Case 2: \(j\) does NOT go to slot \(n\). Element \(j\) must avoid slot \(n\) (in addition to avoiding slot \(j\)). Rename slot \(n\) as "slot \(j\)" — now the \(n - 1\) elements \(\{1, \ldots, n\} \setminus \{n\}\) must form a derangement of their \(n - 1\) positions. That's \(D(n-1)\) ways.

Total: \((n-1) \times (D(n-1) + D(n-2))\).

Verify with \(n = 4\):

\[D(4) = 3 \times (D(3) + D(2)) = 3 \times (2 + 1) = 9\]

---

The Approximation

The IE formula says \(D(n) = n! \sum_{k=0}^{n} (-1)^k / k!\). The Taylor series for \(e^{-1}\) is:

\[e^{-1} = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!}\]

So the sum in the derangement formula is just a truncated version of \(e^{-1}\). Since the terms decrease rapidly (the tail after \(k = n\) is negligible for even moderate \(n\)), you get:

\[D(n) \approx \frac{n!}{e}\]

More precisely, \(D(n)\) is the integer nearest to \(n!/e\) for all \(n \geq 1\).

Probability a random permutation is a derangement:

\[\frac{D(n)}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!} \to \frac{1}{e} \approx 0.3679\]

This converges fast. Already at \(n = 5\): \(D(5)/5! = 44/120 \approx 0.367\). At a party with \(100\) people, the chance nobody gets their own gift back is still roughly \(36.8\%\) — independent of the party size.

---

Partial Derangements

What if you want exactly \(k\) fixed points instead of zero?

Choose which \(k\) elements are the fixed points: \(\binom{n}{k}\) ways. The remaining \(n - k\) elements must have NO fixed points: \(D(n - k)\) ways.

\[\text{Permutations with exactly } k \text{ fixed points} = \binom{n}{k} \cdot D(n-k)\]

Example: Permutations of \(\{1, 2, 3, 4\}\) with exactly \(1\) fixed point:

\[\binom{4}{1} \cdot D(3) = 4 \times 2 = 8\]

Verify: from the \(24\) permutations, subtract \(9\) derangements (0 fixed points), \(6\) with exactly 2 fixed points (\(\binom{4}{2} \cdot D(2) = 6 \times 1 = 6\)), \(0\) with exactly 3 fixed points (\(\binom{4}{3} \cdot D(1) = 4 \times 0 = 0\)), and \(1\) with all \(4\) fixed (the identity). That's \(24 - 9 - 6 - 0 - 1 = 8\). Checks out.

---

Hat-Check Problem Preview

A related question: what's the expected number of fixed points in a random permutation? The answer is \(1\), regardless of \(n\). The proof uses linearity of expectation and is the subject of Ch7 L2. For now, the partial derangement formula gives you the distribution; expectation gives you the average.

---

Computing \(D(n) \bmod p\)

For competitive programming, you need \(D(n) \bmod p\) where \(p\) is typically \(10^9 + 7\). The IE formula is ideal:

\[D(n) = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = \sum_{k=0}^{n} (-1)^k \frac{n!}{k!}\]

Each term \(n! / k!\) is just \(n \times (n-1) \times \cdots \times (k+1)\) — no division needed if you precompute factorials. But it's cleaner to precompute factorial and inverse factorial arrays (using the machinery from Ch5 L1), then compute \(n! \cdot (k!)^{-1} \bmod p\) for each term.

---

The Code

Derangement via IE Formula

Using the modpow function from Ch4 L2 and the factorial precomputation pattern from Ch5 L1:

long long derangementIE(int totalElements, long long mod) {
    assert(totalElements < mod); // If totalElements >= mod, factorial[mod] = 0 and ALL inverse factorials silently become 0. Use a different approach for small primes.
    vector<long long> factorial(totalElements + 1);
    vector<long long> inverseFactorial(totalElements + 1);
    factorial[0] = 1;
    for (int i = 1; i <= totalElements; i++) {
        factorial[i] = factorial[i - 1] * i % mod;
    }
    inverseFactorial[totalElements] = modpow(factorial[totalElements], mod - 2, mod);
    for (int i = totalElements - 1; i >= 0; i--) {
        inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod;
    }
    long long result = 0;
    for (int k = 0; k <= totalElements; k++) {
        long long term = factorial[totalElements] % mod * inverseFactorial[k] % mod;
        if (k % 2 == 0) {
            result = (result + term) % mod;
        } else {
            result = (result - term + mod) % mod;
        }
    }
    return result;
}

\(O(n)\) time, \(O(n)\) space. One modpow call, everything else is multiplication and addition.

Derangement via Recurrence

When you only need a single value of \(D(n)\) and don't want to precompute inverse factorials:

long long derangementDP(int totalElements, long long mod) {
    if (totalElements == 0) return 1;
    if (totalElements == 1) return 0;
    long long twoBack = 1;
    long long oneBack = 0;
    for (int i = 2; i <= totalElements; i++) {
        long long current = (i - 1) % mod * ((oneBack + twoBack) % mod) % mod;
        twoBack = oneBack;
        oneBack = current;
    }
    return oneBack;
}

\(O(n)\) time, \(O(1)\) space. No modular inverse needed — just multiplication and addition.

The recurrence approach is simpler but doesn't give you the factorial/inverse-factorial arrays. If the problem also needs \(\binom{n}{k}\) (e.g., for partial derangements), use the IE approach instead.

---

Common Mistakes

• Forgetting \(D(0) = 1\). The empty permutation is a derangement (vacuously, no element fails the condition). Getting this base case wrong breaks the recurrence. If you define \(D(0) = 0\), every subsequent value is wrong.

• Subtraction without adding mod. In the IE formula, odd-\(k\) terms are subtracted. The expression result - term can go negative. Always write (result - term + mod) % mod to keep values in \([0, \text{mod})\).

• Off-by-one in the IE sum. The sum runs from \(k = 0\) to \(k = n\), not \(k = 1\) to \(k = n\). The \(k = 0\) term is \(n!\) itself (the total number of permutations). Skipping it gives you the size of the union rather than the complement.

---

Quick Recap

• A derangement is a permutation with no fixed points. \(D(n)\) counts them.
• IE derivation: define \(A_i\) = "element \(i\) is fixed." Sizes are \((n-k)!\) for \(k\)-wise intersections. After simplification: \(D(n) = n! \sum_{k=0}^{n} (-1)^k / k!\).
• Recurrence: \(D(n) = (n-1)(D(n-1) + D(n-2))\), with \(D(0) = 1\), \(D(1) = 0\).
• Approximation: \(D(n) \approx n!/e\). The probability a random permutation is a derangement converges to \(1/e \approx 0.368\).
• Exactly \(k\) fixed points: \(\binom{n}{k} \cdot D(n-k)\).

---

Problems

Problem	Link	Difficulty	Focus
CSES — Christmas Party	cses.fi/problemset/task/1717	Easy	Direct application of the derangement formula mod \(10^9 + 7\)
LC 634 — Find the Derangement of an Array	leetcode.com/problems/find-the-derangement-of-an-array	Medium	\(D(n) \bmod 10^9 + 7\) via recurrence or IE formula