Exercise 1606Combinatorics › Counting principlesL1Added 3 Nov 2026

Derangements

#derangements#inclusion-exclusion#permutations

Statement

A derangement is a permutation with no fixed point. Compute the number $D_n$ of derangements of $n$ elements for $n=3,4$ .

Hint

$D_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$ .

Show solutionHide solution

Formula. $D_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!}$ .

For $n=3$ . $D_3=6(1-1+1/2-1/6)=6(1/3)=2$ .

For $n=4$ . $D_4=24(1-1+1/2-1/6+1/24)=24\cdot9/24=9$ .

Conclusion. $D_3=2$ , $D_4=9$ .

Check $n=3$ . Permutations with no fixed point: $(123)$ and $(132)$ . ✓