Derangements

Problem. How many permutations of $n$ elements have no fixed point ($\sigma (i)\ne i$ for all $i$)?

$D_n:1,0,1,2,9,44,265,1854,14833,133496,\dots$

The formulas

By inclusion-exclusion, over which elements are fixed:

$D_n={\sum }_{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})(n-k)!=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}.$

Two recurrences:

$D_n=(n-1)(D_{n-1}+D_{n-2}),D_n=n{D}_{n-1}+(-1{)}^n.$

Asymptotically:

$D_n=\lfloor \frac{n!}{e}+\frac{1}{2}\rfloor ,\frac{D_n}{n!}\to \frac{1}{e}\approx \mathrm{0.3679.}$

So a random permutation has no fixed point about 37% of the time, essentially independent of $n$ — the surprising part.

long long derangement(int n, long long MOD) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    long long a = 1, b = 0;                                // D(0), D(1)
    for (int i = 2; i <= n; i++) {
        long long c = (long long)(i - 1) % MOD * ((a + b) % MOD) % MOD;
        a = b; b = c;
    }
    return b;
}

The first recurrence, explained

Element 1 goes to some position $j$ ($n-1$ choices). Then either:

• $j$ goes to position 1 — the remaining $n-2$ elements form a derangement: $D_{n-2}$;
• $j$ does not go to position 1 — treat “position 1” as $j$‘s forbidden spot, giving a derangement of $n-1$ elements: $D_{n-1}$.

Hence $D_n=(n-1)(D_{n-1}+D_{n-2})$.

Permutations with exactly $k$ fixed points

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)D_{n-k}.$

Choose which $k$ are fixed, derange the rest. Summing over $k$ recovers $n!={\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)D_{n-k}$ — a binomial-transform identity.

Expected number of fixed points is exactly 1, for every $n$, by linearity of expectation: each element is fixed with probability $1/n$.

The generalisation: forbidden positions

Derangements forbid one position per element. The general problem — a permutation avoiding an arbitrary set of forbidden $(i,j)$ pairs — is counted by the permanent of the 0/1 allowed-matrix, which is p-hard. But:

Structure of the forbidden set	Method
One forbidden position each (derangement)	closed form
Forbidden positions form a board with rook-polynomial structure	rook polynomials + inclusion-exclusion
Small $n$	$O(2^{n}n)$ bitmask DP (Ryser’s formula)
Bipartite structure	it is counting perfect matchings — p-hard
Forbidden positions form a staircase	Ménage-like formulas

Rook polynomials

If the forbidden cells form a board $B$, and $r_k$ counts the ways to place $k$ non-attacking rooks on $B$, then

$\#\{\text{permutations avoiding }B\}={\sum }_k(-1{)}^k{r}_k(n-k)!.$

For derangements the board is the diagonal, $r_k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, and the formula collapses to the inclusion-exclusion above.

Related counts

Problem	Answer
Derangements	$D_n\approx n!/e$
Exactly $k$ fixed points	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)D_{n-k}$
Ménage problem (couples, alternating, no adjacent partners)	a separate formula
Permutations with no $i$ mapping to $i$ or $i+1$	$\sum (-1{)}^k(\genfrac{}{}{0ex}{}{2n-k}{k})(n-k)!$
Involutions (${\sigma }^2=\mathrm{id}$)	$I_n=I_{n-1}+(n-1)I_{n-2}$
Permutations with all cycles $\ge 2$	derangements
Permutations with exactly $k$ cycles	Stirling numbers of the first kind
Random permutation has a cycle of length $>n/2$	probability $\ln 2\approx 0.693$

The last row is a nice companion fact, and it is exactly the analysis behind the 100 prisoners problem.

The hat-check problem

$n$ people check hats; the hats are returned at random. The probability nobody gets their own is $D_n/n!\to 1/e$.

It is the standard illustration that inclusion-exclusion over “at least one fixed point” gives an alternating series converging to $e^{-1}$ — and that the answer barely depends on $n$ (already accurate to three decimals at $n=6$).

Why it is worth knowing

Derangements are the smallest non-trivial inclusion-exclusion computation, and the $1/e$ limit is a memorable example of a combinatorial probability converging to a constant. The “exactly $k$ fixed points” formula is also a frequently needed building block in counting problems.

See also: Combinatorics · Special Numbers · Expected Value