# letters and envelopes randomly sent to companies

After having written n job application letters and addressing the n corresponding envelopes, your child does you the kind favor of inserting one letter into each of the envelopes and mailing them. However, she thought all the letters were the same, so that they were placed into the envelopes in a completely random fashion.

(a) What is the probability that all companies get the correct letter?

(b) What is the probability that exactly k are correct?

(c) What is the probability that at least one is correct?

My solution attempt for (a):

The probability that the first company gets the wrong letter is $$1/n$$.

Let's do it for n companies:

$$\frac{1}{n}*\frac{1}{n-1}*\frac{1}{n-2}*...*\frac{1}{n-k}..* \frac{1}{1}$$

Where the last fraction is one because the last company surely will get the correct letter conditioning on the fact that the n-1 companies before got the correct letter.

Hence, my solution for (a) would be:

$$\frac{1}{n!}$$

Is this correct?

(c): This would be equivalent to one minus the complement (that no letter is correct). Again we would have

$$\frac{n-1}{n}*\frac{n-2}{n-1}...*\frac{n-(n-1)}{n-(n-2)}*\frac{0}{1}=0$$

and $$1-0=1$$

b): Here there are n! possible orderings. This means that the first letter could be false, the following k letters correct and the remaining n-k-1 letters false again. Or it could be that the first letters are false, the following k letters correct and the remaining n-k-2 letters false again. And so on (hence n!)

Is my reasoning correct in this case ? What would your solution be for b)? What about a) and b). Are my solutions correct?

Thank you.

More directly you can state that there are $$n!$$ possible arrangements/permutations/outcomes and in exactly one of them we deal with the case described under (a). Then - because the outcomes are equiprobable - we can apply the rule that: $$\text{probability }=\text{ number of favourable outcomes divided by number of possible outcomes}$$
For handling (b) in a similar way you should be familiar with derangements. Here the number of favourable outcomes equals: $$\binom{n}{k}\times!(n-k)=\frac{n!}{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$ First we make a selection of $$k$$ out of $$n$$. They represent the letters with a correct adress. The remaining $$n-k$$ letters have a wrong adress and there are $$!(n-k)$$ derangements on $$n-k$$ objects. Further the number of possible outcomes is again $$n!$$ so applying the rule we find probability:$$\frac1{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$
Based on this we find easily for (c) the probability:$$1-\frac{!n}{n!}=1-\sum_{i=0}^n\frac{(-1)^i}{i!}=\sum_{i=1}^n\frac{(-1)^{i-1}}{i!}$$If $$n$$ is not small then you can also approximate on base of: $$\sum_{i=0}^n\frac{(-1)^i}{i!}\approx e^{-1}$$