Derangements: When Nothing Stays in Place

July 2026 · 18 min read

What Is a Derangement?

A derangement is a permutation of a set in which no element appears in its original position. More formally, given a permutation σ of {1, 2, …, n}, we call σ a derangement if σ(i) ≠ i for every i.

Consider n = 3 with the identity arrangement (1, 2, 3). The six permutations are:

• (1, 2, 3) — not a derangement (all fixed)
• (1, 3, 2) — not a derangement (1 is fixed)
• (2, 1, 3) — not a derangement (3 is fixed)
• (2, 3, 1) — derangement ✓
• (3, 1, 2) — derangement ✓
• (3, 2, 1) — not a derangement (2 is fixed)

So D(3) = 2. This concept appears constantly in competitive programming under various disguises — hat-check problems, secret Santa assignments, permutation mismatch counting, and more.

The Subfactorial D(n)

The closed-form formula for the number of derangements is:

D(n) = n! · ∑_k=0ⁿ (−1)^k / k!

Equivalently, we can write this as:

D(n) = n! · [1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!]

Let’s verify for n = 4:

D(4) = 4! * (1 - 1 + 1/2 - 1/6 + 1/24)
     = 24 * (0 + 0.5 - 0.1667 + 0.0417)
     = 24 * 0.375
     = 9

The nine derangements of {1, 2, 3, 4} are: (2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,3,1,2), (4,3,2,1).

Another useful form uses the nearest-integer function:

D(n) = round(n! / e)   for n ≥ 1

This works because the alternating sum converges to 1/e extremely quickly.

Derivation via Inclusion-Exclusion

The formula emerges naturally from the Principle of Inclusion-Exclusion (PIE). Let A_i be the set of permutations where element i is in its original position (a fixed point). We want the count of permutations with no fixed points:

D(n) = n! − |A₁ ∪ A₂ ∪ … ∪ A_n|

By PIE, the union expands as:

|A₁ ∪ … ∪ A_n| = ∑|A_i| − ∑|A_i ∩ A_j| + …

Now observe:

• |A_i| = (n−1)! — fix one element, permute the rest
• |A_i ∩ A_j| = (n−2)! — fix two elements
• In general, |A_i₁ ∩ … ∩ A_{i_k}| = (n−k)!

There are C(n, k) ways to choose which k elements are fixed, so the k-th inclusion-exclusion term is:

(−1)^k+1 · C(n, k) · (n−k)! = (−1)^k+1 · n! / k!

Summing everything up:

D(n) = n! - [C(n,1)(n-1)! - C(n,2)(n-2)! + C(n,3)(n-3)! - ...]
     = n! - [n!/1! - n!/2! + n!/3! - ... + (-1)^(n+1) * n!/n!]
     = n! * [1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n / n!]

Recurrence Relations

Derangements satisfy two elegant recurrences that are extremely useful for computation.

First Recurrence

D(n) = (n − 1) · [D(n − 1) + D(n − 2)]

Proof sketch: Consider where element 1 goes. Suppose σ(1) = j for some j ≠ 1. There are (n − 1) choices for j. Now two cases arise:

1. σ(j) = 1: Elements 1 and j swap. The remaining n − 2 elements must form a derangement among themselves → D(n − 2) ways.
2. σ(j) ≠ 1: Element j cannot go to position 1. We can think of this as a derangement of n − 1 elements where j plays the role of “the forbidden position” for the remaining mapping → D(n − 1) ways.

Combining: D(n) = (n − 1)(D(n − 1) + D(n − 2)).

Second Recurrence

D(n) = n · D(n − 1) + (−1)ⁿ

This follows directly from the closed-form expansion. It is useful when you want to build a table iteratively with a single previous value.

// Verify: D(4) = 4*D(3) + (-1)^4 = 4*2 + 1 = 9 ✓
// Verify: D(5) = 5*D(4) + (-1)^5 = 5*9 - 1 = 44 ✓

Approximation: D(n) ≈ n!/e

One of the most beautiful facts about derangements is that the probability a random permutation is a derangement converges to 1/e:

P(derangement) = D(n)/n! = ∑_k=0ⁿ (−1)^k/k! → 1/e ≈ 0.3679

The convergence is incredibly fast. Already at n = 5, the probability is 0.3667, differing from 1/e by less than 0.4%. This means:

• For n ≥ 1, D(n) equals the nearest integer to n!/e.
• About 36.8% of all permutations are derangements, regardless of n (for large n).
• The probability that a random permutation has at least one fixed point is approximately 1 − 1/e ≈ 63.2%.

This approximation is surprisingly useful in CP problems that ask about expected values or probabilities related to random permutations.

Computing Derangements

For competitive programming, we usually need D(n) mod p. Here are the standard approaches.

Iterative DP using the First Recurrence

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

long long derangement(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;

    long long prev2 = 1;  // D(0)
    long long prev1 = 0;  // D(1)

    for (int i = 2; i <= n; i++) {
        long long cur = (1LL * (i - 1) % MOD *
                        ((prev1 + prev2) % MOD)) % MOD;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    cout << derangement(n) << "\n";
    return 0;
}

This runs in O(n) time and O(1) space. For most CP problems with n ≤ 10⁶, this is perfectly sufficient.

Precomputing a Table

If you need D(k) for many values of k, precompute the entire table:

const int MAXN = 1000005;
long long D[MAXN];

void precompute() {
    D[0] = 1;
    D[1] = 0;
    for (int i = 2; i < MAXN; i++) {
        D[i] = (1LL * (i - 1) % MOD *
               ((D[i - 1] + D[i - 2]) % MOD)) % MOD;
    }
}

Using the Closed-Form with Modular Inverse

For computing D(n) = n! · ∑(−1)^k/k!, we need modular inverses of factorials:

long long fact[MAXN], inv_fact[MAXN];

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = fact[i - 1] * i % MOD;
    inv_fact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}

long long derangement_closed(int n) {
    long long ans = 0;
    for (int k = 0; k <= n; k++) {
        long long term = fact[n] % MOD * inv_fact[k] % MOD;
        if (k & 1) ans = (ans - term + MOD) % MOD;
        else        ans = (ans + term) % MOD;
    }
    return ans;
}

CP Applications

The Hat-Check Problem

n people check their hats. The hats are returned randomly. What is the probability nobody gets their own hat? Answer: D(n)/n! ≈ 1/e.

Secret Santa Assignments

n people each draw a name for Secret Santa. Nobody should draw themselves. The number of valid assignments is exactly D(n). If you need to generate a random derangement, use a rejection method: generate a random permutation and retry until it is a derangement. Since P ≈ 1/e, the expected number of trials is e ≈ 2.72.

Partial Derangements

Sometimes we need the count of permutations with exactly k fixed points. This equals:

f(n, k) = C(n, k) · D(n − k)

Choose which k elements are fixed, then derange the rest.

// Count permutations of n elements with exactly k fixed points
long long partial_derangement(int n, int k) {
    // C(n, k) * D(n - k)
    long long choose = fact[n] % MOD * inv_fact[k] % MOD
                       * inv_fact[n - k] % MOD;
    return choose % MOD * D[n - k] % MOD;
}

Counting Discordant Permutations

Given two permutations π and σ, the number of positions where π(i) ≠ σ(i) for all i is a generalized derangement problem. Apply the substitution τ = σ⁻¹ ˆ π and count derangements of τ.

Practice Problems

1. Subfactorial (basic): Given n, compute D(n) mod 10⁹+7. Use the recurrence.
2. Fixed points: Given n and k, compute the number of permutations of n elements with exactly k fixed points.
3. At least one match: Given n, compute n! − D(n). How many permutations have at least one fixed point?
4. Generalized derangements: Given a permutation π, count permutations σ such that σ(i) ≠ π(i) for all i.
5. Weighted derangements: Each position i has a “forbidden set” F_i. Count permutations where σ(i) ∉ F_i. (Hint: generalization requires PIE on the forbidden sets.)
6. Expected fixed points: Prove that the expected number of fixed points in a uniformly random permutation is exactly 1, regardless of n. (Hint: linearity of expectation.)
7. Secret Santa with constraints: n people in a circle; nobody can draw themselves or their neighbor. Count valid assignments. (Hint: this is a ménage problem — a harder variant of derangements.)