Derangements and Fixed Points

Concept Overview

A fixed point in a permutation is an element that remains in its original position. A derangement is a permutation with absolutely no fixed points. The number of derangements of n elements, denoted D_n, is the basis for determining the probability mass of any specific number of fixed points k in a uniform random permutation.

Worked Example

Consider a permutation of size n=4. The total number of permutations is n! = 4! = 24. We want to compute the exact probability mass function for the number of fixed points.

First, we compute the derangement counts using the recurrence relation D_m = (m-1)(D_m-1 + D_m-2) with base cases D₀ = 1 and D₁ = 0:

D₀ = 1
D₁ = 0
D₂ = 1 × (0 + 1) = 1
D₃ = 2 × (1 + 0) = 2
D₄ = 3 × (2 + 1) = 9

The number of permutations with exactly k fixed points is given by choosing which k elements are fixed, and then forming a derangement of the remaining n-k elements: C(n,k) D_n-k. For n=4:

k=0: C(4,0) D₄ = 1 × 9 = 9
k=1: C(4,1) D₃ = 4 × 2 = 8
k=2: C(4,2) D₂ = 6 × 1 = 6
k=3: C(4,3) D₁ = 4 × 0 = 0. (Notice exactly n-1 fixed points is impossible, as the last element must also be fixed.)
k=4: C(4,4) D₀ = 1 × 1 = 1

Dividing these counts by 24 gives the exact probabilities: 3/8, 1/3, 1/4, 0, and 1/24.

Experiment

To verify this in the Derangements and Fixed Points module:

Set the Permutation size control to 4.
Set the Fixed points probe control to 2.
Observe the mass exactly matches 1/4 (0.25) in the scrollable count table.
Notice the Derangements D(n) count is 9 and Permutations n! is 24.
Change the Fixed points probe to 3, and confirm the mass is 0.

Limitations

This module is designed to highlight small n exact probability computations. It does not replace exact small n probabilities with a Poisson approximation (which works well for large n). The module restricts permutation size to n ≤ 7 to ensure counts remain within exact integer limits and visually comprehensible. It also distinguishes uniform permutation sampling without replacement from independent choices or bipartite maximum matching.

References

The mathematical background of this principle, specifically distinguishing sampling without replacement and its fixed point distribution from the Poisson approximation, is found in the following resources:

Random Services: Matching - Sampling-without-replacement permutation model, matching indicators and distribution/moment section read; distinguish it from the earlier replacement section.

Derangements and Fixed Points