2005 PMWC Problems/Problem I11

Problem

There are 4 men: A, B, C and D. Each has a son. The four sons are asked to enter a dark room. Then A, B, C and D enter the dark room, and each of them walks out with just one child. If none of them comes out with his own son, in how many ways can this happen?

Solution

This is just a derangement problem (sending the set $\{1,2,3,4\}$ to another set such that none of the original elements are in the same place). The formula is:

\[n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}\]

When $n = 4$, we get:

\[4! \left(\frac{1}{1} - \frac{1}{1} + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right) = 9\]

See also

2005 PMWC (Problems)
Preceded by
Problem I10
Followed by
Problem I12
I: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T: 1 2 3 4 5 6 7 8 9 10