Permutations and distribution problems

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 n balls and n 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 f : \{ 1, \ldots, n \} \to \{ 1, \ldots, n \}. In other words, we’re just assigning each ball to a box. It’s not hard to convince yourself that all such functions f will be equally likely. For this reason, finding the probability reduces to finding how many such f satisfy the additional constraint that 1 has exactly one preimage. That is, we want to count the number of f 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 n^n functions from \{1, \ldots, n\} to itself in total (after all, there are n choices for each of the n elements). How many of these satisfy the constraint? Well, observe that every such f is uniquely determined by first choosing some k \in \{1, \ldots, n\} so that f(k) = 1 (here there are n possibilities), and then choosing what to do with the remaining n-1 elements. What can we do with the remaining ones? Well, we can map them anywhere except 1. Hence at this stage there are (n-1)^{n-1} choices. So we conclude the total number of functions f satisfying the constraints is n(n-1)^{n-1}. This means the desired probability is

\dfrac{n(n-1)^{n-1}}{n^n} = \left( \dfrac{n-1}{n} \right)^{n-1} = \left( 1 - \dfrac{1}{n} \right)^{n-1}.

Curiously, this approaches 1/e as n \to \infty. 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 \sigma : \{ 1, \ldots, n \} \to \{ 1, \ldots, n \}, 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 k with \sigma(k) = k. In other words, the question is asking what the expected number of fixed points of a uniformly randomly chosen permutation of \{1, \ldots, n\} 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 k matches?

This is a bit more difficult, since we now have to determine how many permutations of \{1, \ldots, n\} fix exactly k points. It’s not difficult to see that obtaining such a permutation involves first choosing a k-subset of \{1, \ldots, n\} to fix, of which there are \binom{n}{k}, and then applying a permutation to the remaining n-k 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.


About mlbaker

just another guy trying to make the diagrams commute.
This entry was posted in combinatorics, computer science and tagged , , , , . Bookmark the permalink.

3 Responses to Permutations and distribution problems

  1. At the first part:

    Why isn’t the numerator n! ? After we choose the position of the second ball, there are only n-2 choices left for the third and so on.

  2. ^ Sorry, I read it as what was the probability that every box contained one ball. =P

    I’ll try out the other problems and get back to you if I have I different solution.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s