Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
"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
4  
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
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.