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 people live in n houses and at some instant all of them disappear and reappear in some other house. What is the probability that no two meet each other?

share|improve this question
    
Can more than one person live in a house? –  Torsten Hĕrculĕ Cärlemän Jul 18 '13 at 6:30
    
No,all of them initially are placed in different homes. –  user1907531 Jul 18 '13 at 6:39
    
@EhsanM.Kermani I think the denominator is more complicated than that, since you distinguish between the people when you write $n!$. –  angryavian Jul 18 '13 at 7:08
    
@user14111:yes you are right –  user1907531 Jul 18 '13 at 7:30
    
@user14111:yes n!(1-1!+1/2!..) –  user1907531 Jul 18 '13 at 7:44

1 Answer 1

The question is not completely clear.

I'll answer the following interpretation:

$n \geq 2$ persons live in $n$ houses, one person per house. Now each person is randomly moved to another house, with equal probability for each possibility. What is the probability that after this moving process, there is again exactly one person per house?

The number of possible outcomes is $(n-1)^n$, since for every person there are $n-1$ possibilities (all houses different from the own one). The number of favorable outcomes is the number $!n$ of all fixed-point free permutations, also called derangements. See the wikipedia article for closed expressions for $!n$.

So the probability is $$P(n) = \frac{!n}{(n-1)^n}.$$

For small $n$, we get $$\begin{array}{cc} n & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline P(n) & 100\% & 25\% & 11.11\% & 4.30\% & 1.70\% & 0.66\% \end{array} $$ By the asymtotics of $!n$, we see $$\lim_{n\to\infty} P(n) = 0.$$

share|improve this answer

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.