Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Count Derangements

A derangement is an order in which no item stays in its own place. Start from all n!n! orders and remove those with fixed points by inclusion-exclusion; the result is an alternating sum that is quick to evaluate.

Recognize the task

Items go back to owners or places and none may land in its own: letters in envelopes, hats returned at random, a gift swap where nobody draws their own name, a seating where everyone must move. Test: each item has exactly one forbidden place, and the forbidden places are all different.
Derangements and the notation !n!n are defined in the permutations lesson and derived in the inclusion-exclusion lesson.

Ways to do it

Alternating sumusual
!n=n!∑k=0n(−1)kk!!n = n! \sum_{k=0}^{n} \dfrac{(-1)^k}{k!}
The derangement formula, from inclusion-exclusion on the fixed points.
Recurrencestep up
!n=(n−1)(!(n−1)+!(n−2))!n = (n-1)\big(!(n-1) + !(n-2)\big)
Build up from !1=0!1 = 0 and !2=1!2 = 1 (derangement recurrence).
Nearest whole numbershortcut
!n=round(n!e),n≥1!n = \text{round}\left(\dfrac{n!}{e}\right), \quad n \ge 1
Works because !nn!\frac{!n}{n!} approaches 1e\frac{1}{e} very fast (asymptotic limit).

Steps

StepOn 5 letters in 5 envelopes, none correct
1Check the condition. Every item has one forbidden place, and no item may sit in it.n=5n = 5
2Write the alternating sum. One term for each kk from 00 to nn, signs alternating.!5=5!(1−1+12!−13!+14!−15!)!5 = 5!\left(1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!}\right)
3Multiply n! into each term. Each term becomes the whole number n!k!\frac{n!}{k!}.Factorial ↗120−120+60−20+5−1120 - 120 + 60 - 20 + 5 - 1
4Add. Check: the result is close to n!e\frac{n!}{e}.!5=44!5 = 44

Worked examples

Example 1 · three items

list them
!3=3!(1−1+12−16)=3−1!3 = 3!\left(1 - 1 + \frac{1}{2} - \frac{1}{6}\right) = 3 - 1
alternating sum
22: the orders 231231 and 312312
no digit in its place

Example 2 · six items

recurrence
!4=9!4 = 9, !5=44!5 = 44
known smaller values
!6=5(44+9)!6 = 5(44 + 9)
recurrence with n=6n = 6
265265

Example 3 · exactly two right

choose, then derange
55 letters, exactly 22 in the right envelope
the rest all wrong
(52)=10\binom{5}{2} = 10 ways to pick the correct two
choose the fixed letters
other 33 all wrong: !3=2!3 = 2
derange the rest
10⋅2=2010 \cdot 2 = 20
multiplication principle
Step through all orders of a few items in the permutations visualizer and pick out the ones with no item in place.

See it happen

Start with all n!n! orders and remove those that leave item 11 in place, item 22 in place, and so on. Orders that fix two items were removed twice, so add them back; orders that fix three were added back once too often, so remove them again. Each level has (nk)\binom{n}{k} choices of fixed items and (n−k)!(n-k)! orders of the rest, which is where n!k!\frac{n!}{k!} comes from. For large nn about 37%37\% of all orders are derangements.

Common mistakes

Stopping after one level

✗ !5=120−5⋅4!=0!5 = 120 - 5 \cdot 4! = 0
✓ continue the alternating sum: 120−120+60−20+5−1=44120 - 120 + 60 - 20 + 5 - 1 = 44

Confusing !n with n!

✗ !4=24!4 = 24
✓ 4!=244! = 24 counts all orders; !4=9!4 = 9

Not choosing the fixed items

✗ exactly 22 of 55 right: !3=2!3 = 2
✓ choose the 22 fixed letters first: (52)⋅!3=20\binom{5}{2} \cdot !3 = 20