Exercise 1611Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Derangements via inclusion-exclusion

#derangements#inclusion-exclusion#inclusion

Statement

Compute the number of derangements of $4$ elements using inclusion-exclusion.

Hint

$D_4=\sum_{k=0}^4(-1)^k\binom{4}{k}(4-k)!$ .

Show solutionHide solution

Expand.
$D_4=4!-4\cdot3!+6\cdot2!-4\cdot1!+1\cdot0!=24-24+12-4+1=9.$

Conclusion. $D_4=9$ .

Check. $D_n/n!\to1/e$ ; $9/24=0.375$ , close to $1/e\approx0.368$ .