Five gifts returned so no one gets their own

Question

Five friends each brought one wrapped gift to a party. The gifts get shuffled and handed back, one to each friend. In how many ways can the gifts be returned so that no one receives their own gift?

Accepted Answer

An arrangement where no item lands in its own spot is called a derangement, written Dn. Total ways to hand back 5 gifts is 5! = 120; we need those with zero matches. Inclusion-exclusion (subtract arrangements with at least one person getting their own gift, add back overcounts) gives the formula Dn = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}ight). For n = 5: D5 = 120\left(1 - 1 + 	frac{1}{2} - 	frac{1}{6} + 	frac{1}{24} - 	frac{1}{120}ight) = 60 - 20 + 5 - 1 = 44. A handy check is the recurrence Dn = (n-1)(D{n-1} + D{n-2}) with D3 = 2, D4 = 9:…

Five gifts returned so no one gets their own

Your answer

Discussion

Learn the concepts

Related questions