Derangements: Counting Arrangements With No Fixed Points
How can we count or model shuffles in which nobody receives their own item?
How this lesson unfolds.
Begin with What does a random hat return look like? The sequence then connects Start with the full universe and builds toward Exactly k correct means derange everyone else.
What does a random hat return look like?
A permutation assigns every person exactly one hat; a fixed point occurs when a person receives their own hat.
- Learning goalExplain story setup in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionStart with the full universe
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
How many possible returns are there?
Six distinct hats can be assigned to six people in 6 factorial equals 720 equally likely permutations.
Six distinct hats can be assigned to six people in 6 factorial equals 720 equally likely permutations.
- Learning goalExplain sample space in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionA derangement has no fixed point
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
When does nobody receive their own hat?
A derangement is a permutation pi with pi(i) not equal to i for every position i.
A derangement is a permutation pi with pi(i) not equal to i for every position i.
- Learning goalExplain definition in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionBuild the global count from local indicators
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
How do we count correct hats in one shuffle?
Let I_i indicate that person i receives hat i; then X equals the sum of the six fixed-point indicators.
Let I_i indicate that person i receives hat i; then X equals the sum of the six fixed-point indicators.
- Learning goalExplain indicator count in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionFix one person and count locally
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
What is the chance one chosen person is correct?
For a chosen person, fixing their own hat leaves five factorial arrangements, so P(I_j=1)=5!/6!=1/6.
For a chosen person, fixing their own hat leaves five factorial arrangements, so P(I_j=1)=5!/6!=1/6.
- Learning goalExplain one fixed point in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionThe expected number correct is one
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
What is the average number of correct hats?
Linearity gives E[X]=sum P(I_i=1)=6 times one-sixth equals one, without requiring independence.
Linearity gives E[X]=sum P(I_i=1)=6 times one-sixth equals one, without requiring independence.
- Learning goalExplain expectation in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionOne experiment supports two questions
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
Why is expectation not the whole distribution?
E[X]=1 is a long-run average; the PMF asks the probability of every possible fixed-point count k.
E[X]=1 is a long-run average; the PMF asks the probability of every possible fixed-point count k.
- Learning goalExplain expectation versus pmf in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionThe exact PMF uses derangements
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
What is the probability of exactly k correct hats?
Choose the k fixed people, then derange the other n-k: P(X=k)=C(n,k)D_(n-k)/n factorial.
Choose the k fixed people, then derange the other n-k: P(X=k)=C(n,k)D_(n-k)/n factorial.
- Learning goalExplain fixed point pmf in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionEach person creates one unwanted set
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
How does inclusion-exclusion begin?
Let A_i be the set of complete arrangements fixing person i; each set has size (n-1) factorial.
- Learning goalExplain bad sets in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionSubtracting bad sets removes overlaps twice
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
What counting mistake forces a correction?
An arrangement fixing persons 1 and 2 lies in both A_1 and A_2, so subtracting all single sets removes it twice.
- Learning goalExplain double subtraction in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionPair intersections repair double subtraction
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
Why add overlaps back?
For a chosen pair of fixed people, the remaining n-2 hats can be assigned in (n-2) factorial ways.
- Learning goalExplain pair intersections in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionThree fixed people create three pair overlaps
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
Why must inclusion-exclusion keep alternating?
An arrangement in a triple intersection belongs to three pair intersections, so pair corrections over-add it and a triple correction is required.
- Learning goalExplain triple intersections in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionEvery correction creates the next correction
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
What pattern does the bookkeeping follow?
Inclusion-exclusion alternates subtraction and addition through intersections of every size until each arrangement has the correct net weight.
- Learning goalExplain inclusion exclusion pattern in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionThe derangement formula completes the count
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
How many six-person derangements are there?
D_n=n! times the alternating reciprocal-factorial sum; D_6=265, so the probability of no fixed points is 265/720.
D_n=n!times the alternating reciprocal-factorial sum; D_6=265, so the probability of no fixed points is 265/720.
- Learning goalExplain derangement formula in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionExactly k correct means derange everyone else
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.
How does the full fixed-point distribution fit together?
For each k, choose the fixed positions and derange the rest; k=n-1 is impossible because one remaining person must also be fixed.
For each k, choose the fixed positions and derange the rest; k=n-1 is impossible because one remaining person must also be fixed.
- Learning goalExplain distribution synthesis in the fixed-point model.
- Helpful foundationspermutations · factorials · indicator variables
- Common trapE[X]=1 is an average, not a claim that every shuffle has exactly one fixed point; inclusion-exclusion is needed because bad sets overlap.
- Next connectionUse inclusion-exclusion on a new forbidden-position problem
More context
The portrait diagram moves from an exact formula through three checks, a six-person visual, and one conclusion.