Six coats returned, none to its owner

Question

Six diners check their coats, and the attendant loses the tickets and returns the six coats at random, one to each diner.

In how many ways can the coats be returned so that no diner gets their own coat?

Accepted Answer

This is a derangement of 6 items, D6. Rather than expanding the full series, use the recurrence Dn = (n-1)\left(D{n-1} + D{n-2}ight), building up from known small values D4 = 9 and D5 = 44: D6 = 5\,(D5 + D4) = 5\,(44 + 9) = 5 	imes 53 = 265. (The formula D6 = 720\sum{k=0}^{6}\frac{(-1)^k}{k!} = 265 agrees.) Takeaway. For larger cases the recurrence Dn = (n-1)(D{n-1} + D{n-2}) is fastest. Here D6 = 265.

Six coats returned, none to its owner

Your answer

Discussion

Learn the concepts

Related questions