∑MathIntermediate

Derangements

Key Points

  • •
    A derangement is a permutation with no element left in its original position, often written as !n or D(n).
  • •
    Derangements can be counted by the recurrence D(n) = (n-1)(D(n-1) + D(n-2)) with bases D(0)=1 and D(1)=0.
  • •
    Using inclusion–exclusion, D(n) equals n! times the alternating series sum from k=0 to n of (-1)^k/k! and is very close to n!/e.
  • •
    As n grows, the probability a random permutation is a derangement approaches 1/e ≈ 0.3679.
  • •
    Derangements connect to practical tasks like secret-santa assignments and seat-swapping puzzles where no one keeps their own item.
  • •
    In programming contests, compute D(n) with O(n) time dynamic programming or O(n) modular arithmetic using factorials and inverse factorials.
  • •
    For large exact answers, use big integers (e.g., Boost cp); for modulo answers, carefully handle negative terms.
  • •
    A useful identity is: permutations with exactly k fixed points equal C(n,k)·D(n−k), which decomposes counts by fixed points.

Prerequisites

  • →Basic combinatorics (factorials and binomials) — Derangement formulas use n!, binomial coefficients, and counting arguments.
  • →Inclusion–Exclusion Principle — The closed-form derivation of D(n) relies on inclusion–exclusion over fixed-point events.
  • →Recurrences and dynamic programming — Efficient computation uses the recurrence D(n) = (n−1)(D(n−1)+D(n−2)).
  • →Modular arithmetic (Fermat inverses) — Contest problems often ask for D(n) modulo a prime; computing 1/k! mod M requires inverse factorials.
  • →Big integer arithmetic — Exact values for large n exceed 64-bit capacity and need arbitrary-precision integers.

Detailed Explanation

Tap terms for definitions

01Overview

Derangements are special permutations where no item remains in its original position. If you label n objects 1 through n, a derangement is a reordering such that position i no longer contains item i for every i. The number of such permutations is denoted D(n) or !n (read “subfactorial n”). Derangements arise naturally in problems like Secret Santa: everyone gives a gift, but no one should draw their own name; or in seating arrangements where nobody sits in their assigned seat. Mathematically, derangements are a classic showcase for the inclusion–exclusion principle. Start from n! total permutations; exclude permutations that fix at least one element, then adjust for overcounting by adding back permutations that fix two points, and so on. This produces an elegant closed form that is also a rapidly converging alternating series. There is also a simple dynamic programming (DP) recurrence, D(n) = (n−1)(D(n−1)+D(n−2)), which enables O(n) computation. Derangements connect combinatorics, probability, and asymptotics. A striking fact is that D(n)/n! approaches 1/e as n grows, so roughly 36.79% of all permutations are derangements. In algorithmic practice, these formulas let you compute exact values for moderate n, large values modulo a prime (common in programming contests), or estimate probabilities quickly.

02Intuition & Analogies

Imagine a classroom with n labeled seats and n students holding their assigned seat numbers on cards. A derangement is a seating plan where no student sits in the seat printed on their card. If any student ends up in the seat number they hold, the arrangement is not a derangement. This mirrors Secret Santa: each person draws a name, but nobody should draw their own. Think of it like shuffling keys and locks. You have n keys and n matching locks, one key per lock with the same label. A “deranged” shuffle is one where no key ends up in its matching lock. If you try to place key 1 first, you can put it anywhere except lock 1. Whichever lock you pick creates a chain of constraints: eventually, either a cycle closes neatly or you’re forced to resolve a conflict by swapping choices—this intuition underlies the DP recurrence D(n) = (n−1)(D(n−1)+D(n−2)). The term (n−1) counts the choices for where the first item goes. If the item at that chosen position comes back to the start, you form a 2-cycle and reduce to D(n−2); otherwise, you propagate the constraint, effectively reducing to D(n−1). From a probabilistic angle, imagine drawing a random permutation. For each position i, the chance it remains fixed is 1/n. While these events are not independent, inclusion–exclusion carefully corrects overlaps: we subtract permutations fixing any one position, add back those fixing two, and continue. The alternating add–subtract pattern causes massive cancellations, leaving a simple sum closely approximating n!/e.

03Formal Definition

Let be the symmetric group of all permutations of {1,2,…,n}. A derangement is a permutation \( \) such that \((i) i\) for all \(i \{1,,n\}\). Denote the number of derangements by \(D(n)\) or \(!n\). Using inclusion–exclusion, consider sets \( = \{ : (i) = i \}\) for fixed-point events. Then \[ D(n) = - = (-1)^k (n-k)! = n! . \] This yields the approximation \(D(n) n!/e\), and, more precisely, \(D(n)\) is the nearest integer to \(n!/e\) for \(n 1\). Derangements also satisfy the linear recurrence with constant coefficients: \[ D(0)=1,\; D(1)=0,\; D(n) = (n-1)(D(n-1)+D(n-2)) n 2. \] Another useful identity counts permutations with exactly k fixed points: choose those k positions and derange the rest, giving \( D(n-k)\). The exponential generating function (EGF) encodes all \(D(n)\): \[ D(n) = . \]

04When to Use

  • Counting problems with forbidden fixed positions: Secret Santa assignments, deranged matchings between two identical labeled sets, or seating where no one keeps their assigned seat.
  • Probability estimations: The probability a random permutation has no fixed points converges to 1/e. This is useful for back-of-the-envelope calculations and sanity checks in randomized algorithms.
  • Decompositions by fixed points: If a problem constrains exactly k positions to remain fixed (or be pre-determined), reduce the rest via D(n−k) after choosing which k.
  • Competitive programming: Compute D(n) modulo a prime (e.g., 1,000,000,007) using the DP recurrence or the inclusion–exclusion series with factorials and inverse factorials in O(n) time. Use big integers (Boost cpp_int) for exact large outputs.
  • Asymptotic reasoning: When n is large, replace D(n) by round(n!/e) to guide approximations, test outputs, or derive expected-case behavior.
  • Verification and exploration: For small n, brute force enumeration can confirm understanding and test code that relies on derangement counts.

⚠️Common Mistakes

  • Forgetting base cases: Using the recurrence without D(0)=1 and D(1)=0 gives wrong values. Always seed dp[0]=1 and dp[1]=0.
  • Overflow in 64-bit integers: Values grow like n!, so even D(21) exceeds 64-bit signed limits. Use 64-bit only up to about n=20. For larger n, switch to big integers or compute modulo a prime.
  • Mishandling negative terms modulo M: In inclusion–exclusion mod M, terms alternate signs. Always normalize with (x % M + M) % M to avoid negative residues.
  • Off-by-one in loops: The recurrence starts at n=2; starting at n=1 or mixing indices leads to incorrect dp values.
  • Misusing the approximation n!/e: It is not exact for small n (e.g., D(2)=1, while 2!/e≈0.736). Use rounding to the nearest integer only when you can justify it, and never in exact modular outputs.
  • Confusing EGF with ordinary generating function: The identity (\sum D(n) x^n/n! = e^{-x}/(1-x)) is an exponential generating function; plugging x as a probability or treating coefficients as ordinary may cause mistakes.
  • Assuming independence of fixed-point events: Fixed points are not independent; inclusion–exclusion corrects the dependencies. Don’t multiply (1−1/n)^n to estimate derangements; use the proper limit 1/e.

Key Formulas

Derangement Recurrence

Explanation: The number of derangements of n items can be built from smaller cases by placing item 1 and analyzing whether it forms a 2-cycle or not. This yields an O(n) dynamic programming method.

Inclusion–Exclusion Integer Form

Explanation: Start from all permutations and subtract those fixing at least one position, then add back those fixing two, etc. This counts permutations with no fixed points exactly as an integer sum.

Alternating Series Form

Explanation: Factor out n! from the inclusion–exclusion result to get a rapidly convergent alternating series. It shows D(n) is very close to n!/e.

Asymptotic Probability

Explanation: The fraction of permutations without fixed points approaches 1/e as n grows. This underlies quick probability estimates in large systems.

Nearest-Integer Identity

Explanation: For , D(n) is the nearest integer to n!/e. This gives a highly accurate way to check answers, though not for exact modular arithmetic.

Exponential Generating Function

Explanation: Forbidding 1-cycles (fixed points) in permutations multiplies the EGF by . Combined with the EGF for all permutations 1/(1−x), we obtain /(1−x).

Fixed-Point Decomposition

Explanation: Choose which k positions are fixed, then derange the remaining n−k positions. This partitions permutations by the number of fixed points.

Alternate Recurrence

Explanation: This first-order inhomogeneous recurrence follows from the series definition. It can be useful for proofs or incremental computation with attention to alternating signs.

Expected Fixed Points

\mathbb{E}[\text{# fixed points}] = \sum_{i=1}^{n} \mathbb{E}[I_i] = \sum_{i=1}^{n} \frac{1}{n} = 1

Explanation: Each position is a fixed point with probability 1/n, so the expected number of fixed points in a random permutation is 1. This helps explain why derangements remain a constant-probability event.

Complexity Analysis

There are several practical ways to compute D(n), each with distinct complexity trade-offs. 1) Dynamic Programming via the recurrence D(n) = (n−1)(D(n−1)+D(n−2)) runs in O(n) arithmetic operations and uses O(1) extra space if we keep only the last two values. With 64-bit integers, it works up to roughly before overflow; with big integers, arithmetic cost grows with the number of bits (about O(n log n) bits for values near n!), so the true bit-complexity is higher—roughly O(n·M(B)) where B is the bit-length and M(B) is the complexity of big-integer multiplication. 2) Inclusion–Exclusion as D(n)= (−1)^k(n−k)! also takes O(n) terms. If done with precomputed factorials and inverse factorials modulo a prime, it’s O(n) time and O(n) space. Over integers with big arithmetic, term sizes scale up to n!, so bit-complexity is again dominated by big multiplications/divisions. 3) Alternating series D(n)=n!(−1)^k/k! modulo a prime can be computed in O(n) using factorials and inverse factorials. Care with negative residues is essential. Memory is O(n) for factorial tables (or O(1) if streaming inverses are computed on the fly, which may increase time). 4) Brute-force enumeration of permutations is O(n!) time and O(n) space and is only suitable for as a correctness check or teaching aid. In summary, for exact large n, use big-integer DP (O(n) steps, big-int cost). For modular outputs, precompute factorials and inverse factorials for an O(n) solution. For small n or testing, enumeration works but is factorial-time.

Code Examples

Bottom-up DP for derangements (64-bit, n ≤ 20)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Computes D(n) using the recurrence:
5// D(0)=1, D(1)=0, D(n)=(n-1)*(D(n-1)+D(n-2))
6// Uses 64-bit signed integers; valid up to about n=20 before overflow.
7long long derangement64(int n) {
8    if (n == 0) return 1; // by convention
9    if (n == 1) return 0;
10    long long dnm2 = 1;  // D(0)
11    long long dnm1 = 0;  // D(1)
12    long long dn = 0;
13    for (int i = 2; i <= n; ++i) {
14        // Watch for potential overflow if i > 20
15        dn = (long long)(i - 1) * (dnm1 + dnm2);
16        dnm2 = dnm1;
17        dnm1 = dn;
18    }
19    return dn;
20}
21
22int main() {
23    ios::sync_with_stdio(false);
24    cin.tie(nullptr);
25
26    int n; 
27    if (!(cin >> n)) return 0;
28
29    if (n > 20) {
30        cerr << "Warning: 64-bit overflow likely for n > 20.\n";
31    }
32
33    cout << derangement64(n) << "\n";
34    return 0;
35}
36

Implements the standard derangement recurrence with constant extra memory by keeping only D(n−1) and D(n−2). It is extremely fast and simple, but limited by 64-bit overflow near n=21. Useful for small n, sanity checks, and learning the recurrence.

Time: O(n)Space: O(1)
Exact big-integer derangements via inclusion–exclusion (Boost cpp_int)
1#include <bits/stdc++.h>
2#include <boost/multiprecision/cpp_int.hpp>
3using namespace std;
4using boost::multiprecision::cpp_int;
5
6// Computes factorials up to n using big integers
7vector<cpp_int> factorials(int n) {
8    vector<cpp_int> fact(n + 1);
9    fact[0] = 1;
10    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
11    return fact;
12}
13
14// Compute D(n) = sum_{k=0}^n (-1)^k * C(n,k) * (n-k)!
15cpp_int derangement_big_incl_excl(int n) {
16    auto fact = factorials(n);
17    cpp_int nfact = fact[n];
18    cpp_int ans = 0;
19    for (int k = 0; k <= n; ++k) {
20        // C(n,k) * (n-k)! = n! / k!
21        cpp_int term = nfact / fact[k]; // exact integer division
22        if (k % 2 == 1) ans -= term; else ans += term;
23    }
24    return ans;
25}
26
27int main() {
28    ios::sync_with_stdio(false);
29    cin.tie(nullptr);
30
31    int n; 
32    if (!(cin >> n)) return 0;
33
34    cpp_int Dn = derangement_big_incl_excl(n);
35    cout << Dn << "\n"; // cpp_int prints as full decimal
36    return 0;
37}
38

Uses big integers to compute the inclusion–exclusion formula in an integer-safe way: C(n,k)(n−k)! equals n!/k!, so no fractions appear. This yields exact D(n) for large n, limited only by memory and time for big-integer arithmetic.

Time: O(n) big-int operations (bit complexity grows with n)Space: O(n) big-int storage for factorials
Derangements modulo 1,000,000,007 via alternating series
1#include <bits/stdc++.h>
2using namespace std;
3static const long long MOD = 1000000007LL;
4
5long long modpow(long long a, long long e) {
6    long long r = 1 % MOD;
7    a %= MOD;
8    while (e > 0) {
9        if (e & 1) r = (__int128)r * a % MOD;
10        a = (__int128)a * a % MOD;
11        e >>= 1;
12    }
13    return r;
14}
15
16int main() {
17    ios::sync_with_stdio(false);
18    cin.tie(nullptr);
19
20    int n; 
21    if (!(cin >> n)) return 0;
22
23    // Precompute factorials and inverse factorials up to n
24    vector<long long> fact(n + 1), invfact(n + 1);
25    fact[0] = 1;
26    for (int i = 1; i <= n; ++i) fact[i] = ( (__int128)fact[i - 1] * i ) % MOD;
27    invfact[n] = modpow(fact[n], MOD - 2); // Fermat's little theorem (MOD is prime)
28    for (int i = n; i >= 1; --i) invfact[i - 1] = ( (__int128)invfact[i] * i ) % MOD;
29
30    // Compute D(n) = n! * sum_{k=0}^n (-1)^k / k!   (mod MOD)
31    long long series = 0;
32    for (int k = 0; k <= n; ++k) {
33        long long term = invfact[k]; // 1/k!
34        if (k % 2) term = (MOD - term) % MOD; // apply (-1)^k
35        series += term;
36        if (series >= MOD) series -= MOD;
37    }
38    long long Dn = ( (__int128)fact[n] * series ) % MOD;
39
40    cout << Dn << "\n";
41    return 0;
42}
43

Computes D(n) modulo a large prime using the alternating series form and precomputed factorials/inverse factorials. Negatives are handled by converting −x to MOD−x to keep residues non-negative.

Time: O(n)Space: O(n)
Monte Carlo estimate of derangement probability (~1/e)
1#include <bits/stdc++.h>
2using namespace std;
3
4bool is_derangement(const vector<int>& p) {
5    for (int i = 0; i < (int)p.size(); ++i) if (p[i] == i) return false;
6    return true;
7}
8
9int main() {
10    ios::sync_with_stdio(false);
11    cin.tie(nullptr);
12
13    int n = 10;         // size of permutation
14    int trials = 200000; // increase for better accuracy
15
16    vector<int> p(n);
17    iota(p.begin(), p.end(), 0);
18
19    mt19937 rng((uint32_t)chrono::high_resolution_clock::now().time_since_epoch().count());
20
21    int derangements = 0;
22    for (int t = 0; t < trials; ++t) {
23        shuffle(p.begin(), p.end(), rng);
24        if (is_derangement(p)) ++derangements;
25    }
26
27    double estimate = (double)derangements / trials;
28    cout.setf(ios::fixed); cout << setprecision(6);
29    cout << "Estimated P(derangement) for n=" << n << ": " << estimate << "\n";
30    cout << "1/e ≈ " << setprecision(6) << (1.0/exp(1.0)) << "\n";
31    return 0;
32}
33

Simulates random permutations and counts the fraction that are derangements to empirically observe convergence to 1/e as n grows. Useful for intuition and testing, not for exact answers.

Time: O(trials ¡ n)Space: O(n)