What is the probability that no letter is in its proper envelope?

Question

Five letters are addressed to five different persons and the corresponding envelopes are prepared. The letters are put into the envelopes at random. What is the probability that no letter is in its proper envelope?

Answer 1

This is called Montmort's matching problem. Just Google it. Any short answer I can provide will not have the same clarity or completeness as any you will find on the web! If you still have difficulties, let me know. Or may be someone else will provide an answer.

In case I am not around when you post the comment, the final answer is $$ 44/5! \approx 0.36667$$

The notation that is used is $$ \frac{!5}{5!}$$ where $$ !n = \text{Round}\left(\frac{n!}{e}\right)$$

See https://en.wikipedia.org/wiki/Derangement for more details.

Answer 2

Let $1,2,3,4,5$ be the letters and let $A,B,C,D,E$ be the proper envelope resepctively.

1) In case of five proper envelopes, only $1$ pattern.

2) In case of only four proper envelopes, the last one is in the proper envelope, so $0$ pattern.

3) In case of only three proper envelopes, you have $\binom{5}{3}\times 1=10$ patterns.

4) In case of only two proper envelopes, you have $\binom{5}{2}\times 2=20$ patterns.

For example, for $A=1, B=2,C,D,E$, you have two patterns as $(C,D,E)=(4,5,3),(5,3,4).$

5) In case of only one proper envelope, you have $\binom{5}{1}\times 9=45$ patterns.

For example, for $A,B,C,D,E=5$ you have nine patterns as $$(A,B,C,D)=(2,1,4,3),(2,3,4,1),(2,4,1,3),(3,1,4,2),$$$$(3,4,1,2),(3,4,2,1),(4,1,2,3),(4,3,1,2),(4,3,2,1).$$

Hence, what you want is $$1-\frac{1+0+10+20+45}{5!}=\frac{5!-76}{5!}=\frac{44}{120}=\frac{11}{30}.$$

Answer 3

So let the letters be : A B C D E and the corresponding envelopes are : a b c d e. Now A cannot go to a, so A can for example go to c. Then C has 4 options to go to: a , b, d, and e. The 1st has 2 choices, the 2nd has 3, the 3rd has 3, and the 4th has 3 choices. So there are 2 + 3 + 3 + 3 = 11 choices. Since A has 4 options to go to, the total is then : 11*4 = 44. And there are a total of 5! ways to do so. So then probability is : 44/120. This is perhaps easier to digest than using the full theorem.

Answer 4

Let us have n letters corresponding to which there exist n envelopes bearing different addresses.

A Match occurs if $Letter_{i}$ gets into $Envelope_{i}$ , $Letter_{j}$ gets into $Envelope_{j}$. Let us denote this event as $E_{i}$ .

A NO Match occurs if $Letter_{i}$ gets into $Envelope_{j}$ , $Letter_{j}$ gets into $Envelope_{i}$. Let us denote this event as $\overline{E_{i}}$ .

$E_{i}$ : Denote the Event where that the ith object occupies the ith position corresponding to its number. Then, the probability 'p' that P(None of the objects occupies the place corresponding to its number) = P( No Letter will be in its proper Envelope corresponding to its number) is given by : $ p = P(\overline{E1} \cap \overline{E2} \cap \overline{E3}.... \cap \overline{En} ) = 1 - P(\text{Atleast one of the objects occupies the place corresponding to its number})= 1 - P(\text{Atleast One Letter will be in its proper Envelope corresponding to its number})= 1 - P(E1 \cup E2\cup E3.... \cup En) = 1 - [\sum_{i=1 }^{n}P(E_{i}) - \sum_{i=1 }^{n}\sum_{j=1 }^{n}P(E_{i} \cap E_{j})....+(-1)^{n-1}P(E_{1} \cap E_{2}\cap E_{3}....... \cap E_{n}) ]= 1 - [\frac{\binom{n}{1}}{n} - \frac{\binom{n}{2}}{n(n-1)} + \frac{\binom{n}{3}}{n(n-1)(n-2)} - ..... + \frac{(-1)^{n-1}}{n(n-1)(n-2)...3.2.1} ] = 1- [ 1- \frac{1}{2!} + \frac{1}{3!}-...+\frac{^{(-1)^{(n-1)}}}{n!}]= \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - ........ + \frac{(-1)^{(n)}}{n!} = \sum_{k = 0 }^{n}\frac{(-1)^{k}}{k!}$ ...........................................................................

We know that $e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...$. Putting $x = -1$, $e^{-1}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...$

But for large n :

p = $1-1 + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} - ........... = e^{-1}$

And, the Probability of Atleast One match : $1 - p = (1-e^{-1})$

.........................................................................

Therefore, P(None of the n letters goes to the correct envelope ) = $\sum_{k = 0 }^{n}\frac{(-1)^{k}}{k!}$