A disgruntled secretary problem - why my solution is incorrect

Question

There are $n$ letters addressed to $n$ different people. The $n$ addresses are typed on $n$ envelopes. A disgruntled secretary shuffles the letters and puts them in the envelopes in random order, one letter per envelope.

We are to find the probability that at least one letter is put in a correctly addressed envelope.

---

I tried to solve this problem in the following way:

1. I calculated that there are $n!$ possibilities of inserting the letters into the envelopes.
2. I thought of the envelopes as boxes. So if the letter is put in the correct box that implicates that the letter will be given to the proper person.

So now:

1. imagine one person gets the right letter, that gives us: $${{n} \choose {1}} (n-1)!$$ different situations. ${n\choose1}$ because people are different,
2. imagine two people get the right letter, this case leads to: $${{n} \choose {2}} (n-2)!$$ And so on...

The results above suggest that the searched probability is equal to: $$P(A) = \frac{\sum_{k=1}^n{n\choose k}(n-k)!}{n!}$$ The answer is of course wrong. I've wondered why and I think that the problem lies in calculating the number of people who will be given the right letter, because when we imagine that one person gets the right one and we write ${n \choose 1}(n-1)!$ it doesn't mean that he or she is the ONLY person who gets the right letter, does it?
What is the right answer? Is it: $\sum_{i=1}^n\binom{n}{i}(n-i)!(-1)^{i+1}$? If yes, why?

Answer 1

There are $n!$ ways to distribute $n$ different letters to $n$ different envelopes.

An envelope receives the proper letter: There are $\binom{n}{1}$ ways to select an envelope that receives the proper letter and $(n - 1)!$ ways to distribute the remaining letters to the remaining envelopes. Thus, there are $$\binom{n}{1}(n - 1)!$$ such distributions.

However, have counted too much if $n > 1$. Observe that $\binom{n}{1}(n - 1)! = n!$. However, not all the distributions result in at least one envelope receiving the proper letter if $n > 1$. In particular, we have counted those distributions in which two envelopes receive the proper letter twice, once for each way we could have designated one of those envelopes as being the envelope that receives the proper letter. Thus, we need to subtract these from the total.

Two envelopes receive the proper letter: There are $\binom{n}{2}$ ways to select the envelopes that receive the proper letter and $(n - 2)!$ ways to distribute the remaining envelopes to the remaining letters. Hence, there are $$\binom{n}{2}(n - 2)!$$ such distributions.

Thus far, we have $$\binom{n}{1}(n - 1)! - \binom{n}{2}(n - 2)!$$ distributions. However, if $n > 2$, we have not counted distributions in which three envelopes receive the proper letter at all. The reason for that is we added such cases three times, once for each way we could designate one of those envelopes as the envelope that receives the proper letter, and then subtracted them three times, once for each of the $\binom{3}{2}$ ways we could designate two of those envelopes as the ones that receive the proper letter. Therefore, we need to add those cases to the total, which gives $$\binom{n}{1}(n - 1)! - \binom{n}{2}(n - 2)! + \binom{n}{3}(n - 3)!$$ distributions. However, if $n > 3$, we have added too much.

By the Inclusion-Exclusion Principle, the number of distributions in which at least one envelope receives the proper letter is $$\sum_{k = 1}^{n} (-1)^{k - 1}\binom{n}{k}(n - k)!$$ Hence, the probability that at least one of the randomly distributed letters will be placed in the proper envelope is $$\frac{1}{n!}\sum_{k = 1}^{n} (-1)^{k - 1}\binom{n}{k}(n - k)! = \sum_{k = 1}^{n} (-1)^{k - 1}\frac{1}{k!}$$

Answer 2

I think a simple way to solve this is by using derangements. Notice that $$P(\{ \text{at least one letter is correct}\}) = 1 - P(\{\text{all letters are incorrect} \})$$ so we can compute $P(\{\text{all letters are incorrect} \})$ as follows:

We have to distribute $n$ letters into $n$ envelopes, so $n!$ possibilities for this. Now, in how many ways are all the letters in the incorrect envelope?

This is given by the derangements of the $n$ letters, denoted $!n $, and $$!n=n!\sum_{i=0}^n \frac{(-1)^i}{i!}$$

So then $$P(\{\text{all letters are incorrect} \})= \frac{n!\sum_{i=0}^n \frac{(-1)^i}{i!}}{n!}=\sum_{i=0}^n \frac{(-1)^i}{i!}$$ To which we can conclude that $$P(\{ \text{at least one letter is correct}\}) = 1 - \sum_{i=0}^n \frac{(-1)^i}{i!}.$$

Answer 3

Your answer is wrong because of double counting, as you might have already guessed. Your solution is also quite close to the real answer.

Your solution:

$ans(n) = C(n,1) * g(n-1) + C(n,2) * g(n-2) + ... + C(n,n) * 1$

However, your $g(n)$ is defined as $n!$ which will cause all other possible permutations to occur (hence double counting them in other terms). And that is not what you were looking for, you were looking for 'exactly' one letter in correct box.

So, the definition of g(n) is none of the letters in correct box .

Now, how to find g(n) ?

Isn't it exactly the reverse of the original problem, they form exhaustive set, none in correct box and atleast one in correct box is basically all possible permutations.

So, $ g(n) = n! - ans(n) $

If we substitute in original equation:

$ ans(n) = C(n,1) * ((n-1)! - ans(n-1)) + C(n,2) * ((n-2)! - ans(n-2)) + ... +C(n,n) * 1$

Answer 4

Let us have n letters corresponding to which there exist n envelopes bearing different addresses. Considering various letters being put in various envelopes, a match is said to occur if a letter goes into the right envelope. Let us first consider the event $A_{k}$ when a match occurs at the kth place.

When $A_{k}$ occurs, the kth letter goes to the kth envelope but (n - 1) letters can go to the remaining (n - 1) envelopes in (n - 1)! ways. Therefore : $P(A_{k}) = \frac{(n - 1)!}{n!} = \frac{1}{n}$. $P(A_{k})$ denotes the probability of the kth match

Let us think of a situation : $Letter_{i}$ must get into $Envelope_{i}$ , $Letter_{j}$ must get into $Envelope_{j}$.
2 cases arise.
Case 1 : 'n' different objects 1.2 •...• n are distributed at random in n places marked 1.2 •...• n. Find the probability that none of the objects occupies the place corresponding to its number.

Case 2 : If n letters are randomly placed in correctly addressed envelopes, What is P(Exactly r letters are placed in correct envelopes)= ?

Solutions :

$E_{i}$ : Denote the Event where that the ith object occupies the ith position corresponding to its number. Then, the probability 'p' that None of the objects occupies the place 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(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!}$ ......................................................................

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

The Probability of each of the r letters is in the correct envelope = $\frac{1}{r!}$

If we think, Out of n letters, only r letters are in the correct envelope. Then , the probability that None of the remaining, (n-r) letters are in the correct envelope is given by : $\sum_{k = 0 }^{n-r}\frac{(-1)^{k}}{k!}$

Therefore, P(Out of n letters exactly r letters go to the Correct envelope) is given by :

$\frac{1}{r!}\sum_{k = 0 }^{n-r}\frac{(-1)^{k}}{k!}$