This post is inspired by a few interesting questions I was asked by a friend, who’s currently taking Algorithms II at Carleton University. The first question was
We have balls and boxes. We place each ball in a box, uniformly at random. What is the probability that given a random box, it will contain exactly 1 ball?
At first, this question may seem daunting. However, we can abstract away the superficial details of “balls” and “boxes”, and see the problem for what it really is. It is clear from the problem description that we are choosing a function . In other words, we’re just assigning each ball to a box. It’s not hard to convince yourself that all such functions will be equally likely. For this reason, finding the probability reduces to finding how many such satisfy the additional constraint that 1 has exactly one preimage. That is, we want to count the number of which map one, and only one element to 1. Note that here, 1 is like our fixed “box”, and we want to find how many possible configurations are such that our fixed box has exactly one ball.
Well, having recast this in terms of function counting, it’s no longer so difficult. There are obviously functions from to itself in total (after all, there are choices for each of the elements). How many of these satisfy the constraint? Well, observe that every such is uniquely determined by first choosing some so that (here there are possibilities), and then choosing what to do with the remaining elements. What can we do with the remaining ones? Well, we can map them anywhere except 1. Hence at this stage there are choices. So we conclude the total number of functions satisfying the constraints is . This means the desired probability is
Curiously, this approaches as . Now on to a more interesting example:
We put the balls into the boxes in such a way that there is exactly one ball in each box. If the number written on a ball is the same as the number written on the box containing the ball, we say there is a match. What is the expected number of matches?
The first thing we notice when we read this problem are the phrases “exactly one ball in each box”, and “number written on a ball is the same as the number written on the box containing the ball”. Since we know there are equally many balls and boxes, this problem is screaming “permutations” out to us. That is, if we again view the assignment of balls into boxes as a function , it is clear that in this problem we want to deal with bijective functions (permutations). “Matches”, as they are called above, refer simply to the number of fixed points of the permutation, that is, elements with . In other words, the question is asking what the expected number of fixed points of a uniformly randomly chosen permutation of is. It’s a (perhaps surprising, but still easy) exercise to prove that this is 1.
The final question asks:
What is the probability that there are matches?
This is a bit more difficult, since we now have to determine how many permutations of fix exactly points. It’s not difficult to see that obtaining such a permutation involves first choosing a -subset of to fix, of which there are , and then applying a permutation to the remaining elements which fixes none of them. Such permutations are called derangements. We are now faced with the problem of computing how many derangements there are. This will be the topic of a follow-up post.