Derangements: Formula, Recurrence and Examples

Before this lesson: Permutations and arrangements, Inclusion–exclusion, Counting with recurrences

Your goal: Count permutations that avoid every original position.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Names you may know: permutations with no fixed points; subfactorial.

Derangements: Formula, Recurrence and Examples: the key idea

A derangement is a permutation with no fixed point: no object occupies its original labelled position. Let Dₙ be the count. Inclusion–exclusion on the forbidden fixed positions gives $D_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$ . The useful recurrence is Dₙ=(n−1)(Dₙ₋₁+Dₙ₋₂) for n≥2, with D₀=1,D₁=0. The empty permutation has no fixed point, explaining D₀. Exact counts should use these finite formulas rather than rounding an approximation without justification.

A worked example

Count derangements of three letters A,B,C from positions A,B,C.

The valid orders are BCA and CAB, so D₃=2. Inclusion–exclusion agrees: 3!−3·2!+3·1!−1=6−6+3−1=2.

Your turn: change one thing

Compute D₄.

Try this on paper before opening the explanation.

Compare your reasoning

The recurrence gives D₄=3(D₃+D₂)=3(2+1)=9.

Pause and check

A trap to avoid: Counting permutations that move only some of the objects.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Derive the inclusion–exclusion formula for Dₙ.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Start with n! permutations. For a specified set of k positions forced to be fixed, the remaining n−k objects have (n−k)! orders. There are C(n,k) such sets. Inclusion–exclusion gives $\sum_{k=0}^n(-1)^k\binom nk(n-k)!=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$ .

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. A derangement has how many fixed positions?

Foundation

1
n
n−1
0

Hint

Use the definition.

Answer and reasoning

0. Every object must avoid its own labelled position.

2. What is D₁?

Foundation

0
1
2
−1

Hint

One object has nowhere else to go.

Answer and reasoning

0. The sole one-object permutation fixes that object.

3. What is D₃?

Core

Hint

List BCA and CAB.

Answer and reasoning

2. Only these two permutations avoid all three original positions.

4. What is D₄?

Core

Hint

Use 3(D₃+D₂).

Answer and reasoning

9. 3(2+1)=9.

5. With k specified positions fixed, how many permutations remain?

Stretch

(n−k)!
n!
k!
C(n,k) only

Hint

Arrange the remaining objects freely.

Answer and reasoning

(n−k)!. The n−k remaining positions receive n−k distinct objects.

6. Why is D₀=1?

Stretch

Zero objects have one fixed point
It is a probability
It makes D₁ equal one
There is one empty permutation, with no fixed points

Hint

The empty object is a valid combinatorial outcome.

Answer and reasoning

There is one empty permutation, with no fixed points. The condition of having no fixed point is vacuously satisfied.

7. Which permutation of A,B,C is a derangement from ABC?

Foundation

Hint

Check each original position.

Answer and reasoning

BCA. In BCA, none of A,B,C remains in its original position.

8. What is D₂?

Core

Hint

The two objects must swap.

Answer and reasoning

1. There is exactly one fixed-point-free order of two objects.

9. Why does C(n,k)(n−k)! simplify to n!/k!?

Stretch

n−k must be prime
Every factorial vanishes
The (n−k)! factors cancel
k! always equals one

Hint

Expand the binomial coefficient.

Answer and reasoning

The (n−k)! factors cancel. n!/[k!(n−k)!] times (n−k)! equals n!/k!.

Choose your next step

Continue to Objects and boxes. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.