# Probability for rearranging balls in particular order

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.

-
"What is the probability that we will end up putting one ball in a box." Not clear for me: does it mean: the probability that all boxes have one ball? –  leonbloy Aug 29 '11 at 14:10
The counting you want to do is a famous problem, the problem of Counting Derangements. 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. –  André Nicolas Aug 29 '11 at 14:10

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!}$$

-

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}$$

-
This approach will work, but what you have is full of errors. There are $n!$ possible arrangements, not $(n-1)^n$. $\mathcal{S}_{n,k}$ is the number of permutations that leave at least $k$ points fixed. The paragraph beginning ‘It is easy’ is irrelevant. And the probability is $\frac{S_n}{n!}=\sum\limits_{k=0}^n\frac{(-1)^k}{k!}$, which approaches $1/e$ as $n\to\infty$. –  Brian M. Scott Aug 29 '11 at 21:36
@Thijs: You're right; I wonder how I missed that. In that case the only problems with Sasha’s answer are in the exposition, not the substance. –  Brian M. Scott Aug 30 '11 at 2:47
@Brian Thank you for comments. I have update description for $\mathcal{S}_{n,k}$. –  Sasha Aug 30 '11 at 4:35