SME
Discrete Mathematics · Problem type
Derangements
Use this for “4 letters go into their 4 envelopes at random. In how many ways does no letter reach its own envelope?”
This is an example. Type your own values to start a new problem.
Dₙ
=
round(
n
!
÷
e)
p
=
Dₙ
!
Formulas
Dₙ
=
round(
n
!
e
)
9
=
round(
4!
e
)
p
=
Dₙ
n
!
0.375
=
9
4!
Assumptions
•
A derangement puts no item in its own place; all n! orders are equally likely.
•
By inclusion–exclusion Dₙ = n!(1 − 1 ÷ 1! + 1 ÷ 2! − … ± 1 ÷ n!).
•
That sum is n! ÷ e to within ½, so Dₙ is n! ÷ e rounded to the nearest whole number.
Step-by-step
WE KNOW
n = 4
FIND
derangements (Dₙ), chance none is in place (p)
Step 1 · Find derangements (Dₙ)
Use Dₙ = round(n! ÷ e)
The
inclusion–exclusion
sum
is
within
1
2
of
n
!
e
,
so
round
n
!
e
.
Dₙ
=
round(
4!
e
)
4! = 4 × 3 × 2 × 1 = 24
round(
24
e
)
=
round(8.8291)
=
9
Dₙ = 9
Step 2 · Find chance none is in place (p)
Use p = Dₙ ÷ n!
Of
the
n
!
equally
likely
orders,
Dₙ
leave
nothing
in
place;
it
tends
to
1
e
≈
0.3679.
p
=
9
4!
p
=
0.375
Check
Put the numbers back in. Both sides should match.
9
=
round(
4!
e
)
✓
0.375
=
9
4!
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Combinatorics
Main lesson
Identical items into boxes
Use this for “In how many ways can 10 identical balls go into 4 boxes? With at least one in each box?”
The pigeonhole principle
Use this for “Among 50 people, at least how many share a birth month? How many people force 5 in one month?”
Words with repeated letters
Use this for “How many different words can be made from all 11 letters of MISSISSIPPI?”