0
$\begingroup$

I have been given the following problem:

There are $n$ envelopes and $n$ letters, randomly assigned. Let $A_i =$ the event where the $i$th letter goes to the $i$th envelope (a match). Then $P(A_i)=\frac{(n-1)!}{n!}, P(A_i \cap A_j)= \frac{(n-2)!}{n!},...,P(A_i \cap ... A_n)=\frac{(n-n)!}{n!}=\frac{1}{n!}$

  1. Find the probability of at least one match

  2. Find the probability of no matches

To get a feel for the problem, I let $n=10$ and started evaluating probabilities. For example, when $n=10$, $P(A_i)=\frac{(10-1)!}{10!}=\frac{9!}{10!}=\frac{1}{10}$. Substituting $n$ back in for $10$ gives $P(A_i)=\frac{1}{n}$. Sure enough, as I increased the number of matches while doing this I confirmed that $P(A_i \cap ... A_n)=\frac{(n-n)!}{n!}=\frac{1}{n!}$.

Now, I know that $P$(no matches) = $1-P($at least one match) so answering either of these questions will make answering the other one trivial. My question though, is this: is it correct to think of $P(A_i)=\frac{1}{n}$ as the probability that at least one envelope matches or is $P(A_i)=\frac{1}{n}$ the probability that exactly one envelope matches? If it is the latter, how do I go about answering question 1?

$\endgroup$

1 Answer 1

2
$\begingroup$

No, $P(A_i)=\frac 1n$ is the probability that a given envelope matches its letter. Permutations where no items are fixed are called derangements. For large $n$ the probability is $\frac 1e$. $10$ is rather large, so you will be close. Even for smaller $n$, if you round $\frac {n!}e$ you get the right answer.

$\endgroup$
2
  • $\begingroup$ Hello. We have not covered derangements in my course. Is there another way to go about this? $\endgroup$
    – user821449
    Commented Sep 5, 2020 at 3:05
  • $\begingroup$ That is specifically the set of permutations you are trying to count. If you count them any other way, you are reproducing the approach found in the Wikipedia article. I don't know what your class is expecting. $\endgroup$ Commented Sep 5, 2020 at 3:26

You must log in to answer this question.