# The Matching Problem/Derangements - n letters to n people

There are n letters addressed to n eople at different addresses. 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.

Find the probability that at least one letter is put in a correctly addressed envelope. [Hint: use the inclusion-exclusion formula.] What is the probability approximately, for large n ?

My attempt at a solution:

$$P(\text{all correct}) = \frac{1}{n!}$$

$$P(\text{n-1 correct}) = {n \choose n-1} \frac{1}{n!} = \frac{1}{1!(n-1)!}$$, since $${n \choose n-1}$$ ways of selecting n-1 correct letters.

$$P(\text{n-2 correct}) = {n \choose n-2} \frac{1}{n!} = \frac{1}{2!(n-2)!}$$

$$\ldots$$

$$P(\text{n-n correct}) = {n \choose n-n} \frac{1}{n!} = \frac{1}{n!(n-n)!} = \frac{1}{n!}$$

This all looks ok to me, but I tested this for a case of 4 people, (I think the theoretical value should be $$\frac{9}{24}$$ but obviously that is not what I got. Can someone correct my logic please? Also, with regards to the hint about inclusion/exclusion - where would that come in?

I read about derangements on Wikipedia but it did not make total sense to me (the derivation).

I would appreciate any advice whatsoever including references to other material.

• You use the word derangements in your title, so presumably you are aware that the number of cases with at least one correctly addressed envelope is $n!$ minus the number of derangements (no envelopes correctly addressed). Commented Feb 4, 2015 at 3:29
• For example, the probability $n-1$ are correct is not right. For we cannot have exactly $n-1$ letters in the right envelopes. Commented Feb 4, 2015 at 3:31

Let $S$ be a subset of the letters. We denote by $f(S)$ the number of arrangements in which all of the letters of $S$ (and possibly some others) all get in the correct envelope.

Clearly $f(S)=(n-|S|)!$

Using inclusion exclusion the number of arrangements with at least one correct letter is :

$\sum\limits _{i=1}^n\binom{n}{i}(n-i)!(-1)^{i+1}=\sum\limits_{i=1}^n\frac{n!}{i!}=n!\sum_{i=1}^{n}\frac{-1^{i+1}}{i!}$. Therefore the fraction of arrangements that are derangements is $\sum_{i=1}^{n}\frac{-1^{i+1}}{i!}$ which approaches $\frac{e-1}{e}$ as $n$ goes to infinity.

• Reading over this a few times helped a lot. Thanks. Commented Feb 4, 2015 at 4:02
• Question: Why do we need inclusion-exclusion? I realize what we are doing is essentially choosing i out of n to be correct and $(n-i)!$ refers to how many times we can rearrange the rest. But why should we need to subtract out the cases for i>1? Commented Feb 4, 2015 at 4:18
• Because otherwise you would be counting the function that sends every letter to its own envelope $2^n$ times. Since it is counting in $f(S)$ for every $S$. Commented Feb 4, 2015 at 4:20
• Ah I see now. Thank you very much. Commented Feb 4, 2015 at 4:28

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

By the inclusion-exclusion principle, a Set $$B$$ containing $$N$$ distinct objects, with set of properties $$B_1, B_2, \ldots, B_n$$ (that the objects of the set $$B$$ may possess), and $$N(B_i)$$ being the number of objects having property $$B_i$$,the number of objects in $$B$$ having none of the properties $$B_1, B_2, \ldots, B_n$$ is given by

$$N\left(\bigcap\limits_{i=1}^{n}\bar{B_i}\right)=N-N\left(\bigcup\limits_{i=1}^{n}B_i\right)$$

$$=N-\left(\sum\limits_{i=1}^{n} N(B_i)-\underset{1\leq i\neq j \leq n}{\sum\sum}N(B_i\cap B_j)+\underset{1\leq i\neq j \neq k \leq n}{\sum\sum\sum}N(B_i\cap B_j \cap B_k) - \ldots + (-1)^n N\left(\bigcap\limits_{i=1}^n B_i\right)\right)$$

Now, for the derangement problem, with the set of letters $$A=\{l_1,l_2,\ldots,l_n\}$$ and the set of envelops $$B=\{e_1,e_2,\ldots,e_n\}$$, s.t., $$|A|=|B|=n$$, and let's define the property $$B_i$$ as the match in $$i^{th}$$ position (i.e., we have $$l_i$$ is in $$e_i$$), $$\forall{i\in\{1, 2, \ldots, n\}}$$, with $$N=n!$$ being total number of possible arrangements (permutations) of $$n$$ letters into $$n$$ envelops.

Then we have the number of derangements

$$=N\left(\bigcap\limits_{i=1}^{n}\bar{B_i}\right)$$

$$=n!-\left(n(n-1)!-{n \choose 2}(n-2)!+\ldots (-1)^{n-1}{n \choose n-1}1!\right)$$

$$=\sum\limits_{k=0}^{n}(-1)^k{n \choose k}(n-k)!$$

(Notice the similarity of the above expression with that of Number of onto functions)

Hence, probability of derangement

$$= \frac{\sum\limits_{k=0}^{n}(-1)^k{n \choose k}(n-k)!}{n!}$$, by classical definition

$$=1-\left(1-\frac{1}{2!}+\frac{1}{3!}-\ldots+(-1)^n\frac{1}{n!}\right)$$

$$=\frac{1}{2!}-\frac{1}{3!}+\ldots-(-1)^n\frac{1}{n!}$$

$$\therefore$$ probability that at least one letter is put in a correctly addressed envelope $$= 1-\frac{1}{2!}+\frac{1}{3!}-\ldots+(-1)^{n+1}\frac{1}{n!}$$