Derangement: Definition & Examples

A derangement is a permutation of distinct objects in which none remains in its original position. It counts complete one-to-one reassignments when every original match is forbidden. For a uniformly random shuffle, the count gives the probability that every label moves.

Write $\pi(i)$ for the label occupying slot $i$ . A fixed point occurs when $\pi(i)=i$ ; a derangement satisfies $\pi(i)\ne i$ for every slot. This is a restriction on positions, not on whether labels remain adjacent or form pairs.

Four labels, nine complete moves

Start with labels 1, 2, 3 and 4 in their matching slots. The arrangement $(2,1,4,3)$ is a derangement: two pairs swap. In contrast, $(2,1,3,4)$ is not, because labels 3 and 4 stay put. A derangement need not be one long cycle.

Of the

4!=24

permutations, exactly nine have no fixed points. If all 24 are equally likely, the probability is

\mathbb{P}(\text{no fixed points})=\frac{9}{24}=\frac{3}{8}=37.5\%.

Nine four-label derangements are listed. Among all 24 permutations, the counts with zero, one, two, three and four fixed points are 9, 8, 6, 0 and 1. The no-fixed-point probability is 37.5%; the average fixed-point count is 1.

Exact enumeration of four distinct labels. Read each listed arrangement from slot 1 to slot 4; every label differs from its slot number.

Count by removing fixed points

Let $D_n$ , also written $!n$ , be the number of derangements of $n$ labels. For any specified $k$ slots, fixing their matching labels leaves $(n-k)!$ ways to arrange the rest. There are $\binom{n}{k}$ choices of these slots.

Simply subtracting permutations that fix each individual slot removes some permutations repeatedly. The inclusion-exclusion principle corrects these overlaps, alternately restoring and subtracting intersections:

D_n=\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)! =n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}.

For four labels, this gives

D_4=24-24+12-4+1=9

. For five,

D_5=44

. The boundary counts are

D_0=1

(one empty arrangement) and

D_1=0

. Dennis White's university notes derive the count using the same fixed-position events.

Counting and Combinatorics develops the factorial and binomial counting tools used here. Its public preview gives the outline; the full Library lesson requires membership.

What the probability does—and does not—say

Dividing by

n!

is valid under a uniform distribution over all permutations. Then

\mathbb{P}(\text{no fixed points}) =\sum_{k=0}^{n}\frac{(-1)^k}{k!} \longrightarrow e^{-1}\approx0.367879.

The limit is about

36.8\%

, not an exact finite-

n

probability. For four labels, use

37.5\%

. Berkeley's matching-problem chapter distinguishes the finite sum from this approximation.

Each slot has probability

1/n

of being fixed. Summing these probabilities shows that the expected number of fixed points is one for every

n\ge1

. That is an average over shuffles. The figure includes outcomes with zero, two and four fixed points. For

n\ge2

, different slots’ fixed-point events are dependent, so multiplying their individual no-match probabilities does not give the derangement probability.

A biased shuffle, extra forbidden assignments or indistinguishable objects changes the counting or probability model. In quantitative research, forbidding original label matches can define a reassignment scheme, but it does not itself justify a statistical permutation test: the null model must still permit those rearrangements.

Sources

Dennis White, Inclusion-Exclusion and Derangements, University of Minnesota, 18 October 2010, pp. 3–4: uniform permutation model, fixed-position intersections and Theorem 2.
Berkeley Data 140, §5.3: The Matching Problem, §§5.3.1–5.3.3: matching probabilities, exact no-match probability and large- $n$ approximation.

Four labels, nine complete moves

Count by removing fixed points

What the probability does—and does not—say

Sources

Related terms

Expected value

Permutation