5
$\begingroup$

Given $N$ boxes, each containing one ball each say numbered as $B_1, B_2, B_3, \ldots, B_N$.

We take all of these balls out and put them back in different boxes but not their original one. So, $B_1$ can be put in box $B_2, B_3, B_4, \ldots, B_N$.

We can put more than one ball in a box given that the previous condition holds. What is the probability that we will end up putting one ball in a box.

I am unable to solve it. Total number of cases will be $(N-1)^N$. But when calculating favorable cases I am unable to give do so correctly. If I at first put the first ball ($B_1$) back, then it has $N-1$ places to choose from. Suppose I put back it in 2nd box. Then the 2nd ball ($B_2$) has again $N-1$ positions to choose from. But if first it put back into any other box except $1$ and $2$, then $B_2$ ball has only $N-2$ positions to choose from.

  • 4
    The counting you want to do is a famous problem, the problem of [Counting Derangements.](http://en.wikipedia.org/wiki/Derangement) There are many solutions, some of which are sketched in the link above. Your observation is a good beginning for finding a recurrence for the number of derangements.2011-08-29

2 Answers 2

1

As André Nicolas pointed out, this is the classical problem of counting derangements. Here is one possible solution.

Let $A_N$ be the number of ways to allocate the $N$ balls to the $N$ boxes such that none of the balls goes back to the box it came from. Let us write $i \to j$ if ball $i$ goes into box $j$. First, for some $j \in 2, \ldots, N$ we have $1 \to j$. This can be done in $N - 1$ ways. We now distinguish two cases.

  • If $j \to 1$, then we have $N - 2$ balls $2, \ldots, j-1, j+1, \ldots, N$ left, and exactly the $N - 2$ boxes $2, \ldots, j-1, j+1, \ldots, N$ they came from. So the remaining balls can be allocated in $A_{N - 2}$ ways.

  • If $j \not\to 1$, then we are left with $N - 1$ balls $2, \ldots, j-1, j, j+1, \ldots, N$, which cannot go in the boxes $2, \ldots, j-1, 1, j+1, \ldots, N$ respectively. So the remaining balls can be allocated in $A_{N-1}$ ways.

Since there are $N-1$ ways to choose $j$, we get the recurrence relation

$A_N = (N-1) A_{N-2} + (N-1) A_{N-1}$

This is exactly the same recurrence relation as the recurrence relation of the factorial function $N! = N \cdot (N-1) \cdot \ldots \cdot 2 \cdot 1$. However, for the factorial function we have $0! = 1$ and $1! = 1$, while we have $A_0 = 1$ and $A_1 = 0$. Therefore if we rewrite (*) it to a simpler recurrence relation, we get

$A_N = N \cdot A_{N-1} + (-1)^N$

(while the factorial function has simply $N! = N (N-1)!$). This can then be reduced (**) to other forms, like

$A_N = N! \cdot \sum_{i = 0}^N \frac{(-1)^i}{i!}$

Finally, you are interested in the probability that all balls are assigned to distinct boxes. This is exactly

$p_N = \frac{A_N}{(N-1)^N}$

You could use e.g. Stirling on the factorial in $A_N$ to get

$N! = N \cdot (N-1)! \approx N \frac{(N - 1)^{N - 1}}{e^{N - 1}} \sqrt{2 \pi (N - 1)}$

Then for the ratio you want, you get

$p_N = \frac{A_N}{(N-1)^N} \approx \frac{N}{(N - 1)^N} \cdot \frac{(N - 1)^{N - 1}}{e^{N - 1}} \sqrt{2 \pi (N - 1)} \cdot \sum_{i = 0}^N \frac{(-1)^i}{i!}$ $= \frac{\sqrt{2 \pi N}}{e^{N - 1}} \sqrt{\frac{N}{N - 1}} \sum_{i = 0}^N \frac{(-1)^i}{i!}$

For large $N$, the sum converges to $e^{-1}$, while $N/(N-1) \approx 1$, giving a probability of

$p_N \approx \frac{\sqrt{2 \pi N}}{e^N}$


(*) This can be done using induction on $N$. The induction step:

$A_N = (N-1) A_{N-1} + (N-1) A_{N-2} = N A_{N-1} - A_{N-1} + (N-1) A_{N-2}$ $ = N A_{N-1} - \left((N-1) A_{N-2} + (-1)^{N-1}\right) + (N-1) A_{N-2} = N A_{N-1} + (-1)^N$

(**) This can be done using induction on $N$. The induction step:

$A_N = N \cdot A_{N-1} + (-1)^N = N \cdot (N-1)! \cdot \left(\sum_{i = 0}^{N-1} \frac{(-1)^i}{i!}\right) + N! \frac{(-1)^N}{N!}$ $ = N! \cdot \left(\sum_{i = 0}^{N - 1} \frac{(-1)^i}{i!} + \frac{(-1)^N}{N!}\right) = N! \cdot \sum_{i = 0}^{N} \frac{(-1)^i}{i!}$

1

The total number of possible rearrangements is $(n-1)^n$ as you observed. In order to find the number of target configurations, we can use inclusion-exclusion principle. To this end observe that the target configuration is a permutation that has no fixed points, i.e. does not leave any ball in its original urn. Now

$ S_n = \sum_{k=0}^n (-1)^k \mathcal{S}_{n,k} = \sum_{k=0}^n (-1)^k (n-k)! \binom{n}{k} = \sum_{k=0}^n (-1)^k \frac{n!}{k!} $ where $\mathcal{S}_{n,k}$ is the number of permutations that leave at least $k$ points fixed.

It is easy to see that

$ S_n = (-1)^n + n S_{n-1} \qquad \qquad S_{n-1} = (-1)^{n-1} + (n-1) S_{n-2} $ Adding these two gives $S_n = (n-1)(S_{n-1} + S_{n-2})$. The number $S_n$ is know as subfactorial, or the number of derangements.

Thus the probability is

$ p_n = \frac{S_n}{(n-1)^n} \approx_{n \to \infty} \sqrt{2 \pi n} \, \mathrm{e}^{-n} $

  • 0
    @Brian Thank you for comments. I have update description for $\mathcal{S}_{n,k}$.2011-08-30