Question

A magic bag contains infinitely many balls labeled 1 to n with each ball being equally likely to be drawn from the bag. There are also n boxes labeled 1 to n. Suppose you fill the boxes by choosing a random ball from the magic bag. A match occurs when the ball labeled i is placed in the box labeled i. For an arbitrary k in {0,1,...,n} what is the probability that you have k matches? What is the probability as n tends to infinity?

Answer 1

Let Ai denote the event that i^th ball goes into the i^th box. Then the probability that none of n balls goes to the correct box is :

----------------------------(***)

The probability that each of the k balls are in the right box is :

,

and the probability that none of the remaining (n-k) balls go in the correct boxes is obtained by replacing n by (n-k) in (***)
and is thus given by:
.

Hence by compound probability theorem, the probability that out of n balls exactly k go to the correct boxes is:

Since k balls can go to n boxes in nC_k mutually exclusive ways the required probability of exactly r balls going to correct boxes is

Now when n is large :