Four guests, four rooms, all used

Question

Four guests each independently choose one of 4 rooms, uniformly at random (more than one guest may pick the same room). What is the probability that all four rooms are occupied?

Accepted Answer

There are 4^4 = 256 equally likely choices. When the number of balls equals the number of bins, "all bins occupied" means every guest lands in a different room, so no two collide. You can see this directly: the first guest may take any room, the second must avoid the first (3 of 4 rooms), the third must avoid two rooms (2 of 4), the fourth is forced (1 of 4): \frac{4}{4}\cdot\frac{3}{4}\cdot\frac{2}{4}\cdot\frac{1}{4} = \frac{4!}{4^4} = \frac{24}{256} = \frac{3}{32} \approx 0.09375. Inclusion-exclusion gives the same surjection count: 256 - 4\cdot 3^4 + 6\cdot 2^4 - 4\cdot 1^4 = 256 - 324 + 9…

Four guests, four rooms, all used

Your answer

Discussion

Learn the concepts

Related questions