The Matching Problem/Derangements - n letters to n people

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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